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