 | | The binary search is one of the most efficient methods for searching large tables. Given a table of n entries, a binary search compares the item to be found against item n/2 in the table. If the item to be found is “less” than the item in the middle of the table, it then looks at the item halfway between the start of the table and the middle of the table. If the item to be found is “more” than the item in the middle of the table, it then looks at the item halfway between the middle of the table and the end of the table. This process continues, dividing the search space in half each time, until the item is found or not. In order for a binary search to work, the table must be sorted into increasing order. On average, log2 n comparisons are performed to find any item in the table. Even for large tables, this is very efficient—a table of one million entries only requires 20 comparisons to find any item in the table. | |
|