Implementation and Analysis of Binary Search
Binary search works fundamentally by dividing a sorted set of
data repeatedly and inspecting the element in the middle of each
division. In the implementation presented here, the sorted set of data
resides in sorted, a single block of
contiguous storage. The argument target is
the data we are searching for.
This implementation revolves around a single loop controlled by
the variables left and
right, which define the boundaries of the
current set in which we are focusing our search (see Example 12.8). Initially, we set
left and right
to and size - 1, respectively. During each
iteration of the loop, we set middle to the
middle element of the set defined by left
and right. If the element at
middle is less than the target, we move the
left index to one element after middle.
Thus, the next set searched is the upper half of the current set. If
the element at middle is greater than the
target, we move the right index to one element before
middle. Thus, the next set searched is the
lower half of the current set. As the search continues,
left moves from left to right, and
right moves from right to left. The search
terminates once we encounter the target at
middle, or when
left and right
cross, if the target is not found. Figure
12.8 illustrates this process.

The runtime complexity of binary search depends ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access