The mother of all divide-and-conquer algorithms is binary search, which is a fast algorithm for searching in a sorted array of keys .
To search for key , we compare to the middle key .
- If appears before it must reside in the left half of
- If not, it must reside in the right half of S.
- By repeating this process recursively on the correct half, we locate the key in a total of comparisons — a big win over the comparisons expected using sequential search.