Java Reference
In-Depth Information
the middle element, which counts as one comparison, and then search either the left
or the right subarray, we have
(
n
2
)
T(n) =T +1
Using the same equation,
(
n
2
) (
n
4
)
T =T +1
By plugging this result into the original equation, we get
(
n
4
)
T(n) =T +2
That generalizes to
(
2
k
)
T(n) =T
+k
As in the analysis of merge sort, we make the simplifying assumption that n is a
power of 2, n=2
m
, where m=log
2
(n). Then we obtain
T(n) =1 + (n)
log
2
Therefore, binary search is an O(log(n)) algorithm.
653
654
That result makes intuitive sense. Suppose that n is 100. Then after each search, the
size of the search range is cut in half, to 50, 25, 12, 6, 3, and 1. After seven
comparisons we are done. This agrees with our formula, because log
2
(100) ʆ
6.64386, and indeed the next larger power of 2 is 2
7
= 128.
A binary Search locates a value in an array in O(log(n)) steps.
Because a binary search is so much faster than a linear search, is it worthwhile to sort
an array first and then use a binary search? It depends. If you search the array only
once, then it is more efficient to pay for an O(n) linear search than for an O(n log(n))
sort and an O(log(n)) binary search. But if you will be making many searches in the
same array, then sorting it is definitely worthwhile.
