Search

The Need for Fast Lookup If you have a large list of data (e.g., all font character pointers, or a list of game variables) that is sorted alphabetically or numerically, checking every item sequentially (`memchr′ in Part 89) is inefficient. Binary Search is the solution: it finds the target by repeatedly dividing the search space in half. The Principle: After each comparison, the algorithm eliminates half of the remaining elements. This makes the search time logarithmic, drastically speeding up large lookups. ...

The Need for Block Search and Compare In system programming, you need routines to: Search (memchr): Find the first occurrence of a specific character (e.g., a null terminator, space, or command byte) within a buffer. Compare (memcmp): Verify that two large blocks of memory (e.g., two versions of a game level, or a password against a stored hash) are identical. Routine 1: Block Search (memchr) Block Search scans a memory area for the first occurrence of a specific 8-bit value. ...