... 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
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.