... continues with only the first half (i.e., the first element up to, but not including, the middle element). If the search key is greater than the middle element, the search key cannot match any element in the array’s first half so the algorithm continues with only the second half (i.e., the element after the middle element through the last element). Each iteration tests the middle value of the array’s remaining elements. If the element does not match the search key, the algorithm eliminates half of the remaining elements. The algorithm ends either by finding an element that matches the search key or by reducing the sub-array to zero size.

Binary Search of 15 Integer Values

As an example, consider the sorted 15-element array

 2 3 5 10 27 30 34 51 56 ...

Get C++ How to Program, 10/e now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.