Algorithm analysis - Data Structures and Problem Solving Using Java - page 208

Analyzing successful and unsuccessful searches separately is typical. Unsuc-
cessful searches usually are more time consuming than are successful
searches (just think about the last time you lost something in your house). For
sequential searching, the analysis is straightforward.

An unsuccessful search requires the examination of every item in the
array, so the time will be . In the worst case, a successful search, too,
requires the examination of every item in the array because we might not find
a match until the last item. Thus the worst-case running time for a successful
search is also linear. On average, however, we search only half of the array.
That is, for every successful search in position i , there is a corresponding suc-
cessful search in position (assuming we start numbering from 0).
However, is still . As mentioned earlier in the chapter, all these
Big-Oh terms should correctly be Big-Theta terms. However, the use of Big-
Oh is more popular.

A sequential search
is linear.

O ( N )

N - 1 - i

N ⁄ 2 O ( N )

5.6.2 binary search

If the input array has been sorted, we have an alternative to the sequential
search, the binary search , which is performed from the middle of the array
rather than the end. We keep track of low and high , which delimit the portion
of the array in which an item, if present, must reside. Initially, the range is
from 0 to . If low is larger than high , we know that the item is not
present, so we return NOT_FOUND . Otherwise, at line 15, we let mid be the half-
way point of the range (rounding down if the range has an even number of
elements) and compare the item we are searching for with the item in position
mid . 5 If we find a match, we are done and can return. If the item we are search-
ing for is less than the item in position mid , then it must reside in the range low
to mid-1 . If it is greater, then it must reside in the range mid+1 to high . In
Figure 5.11, lines 17 to 20 alter the possible range, essentially cutting it in
half. By the repeated halving principle, we know that the number of iterations
will be

If the input array is
sorted, we can use
the binary search ,
which we perform
from the middle of
the array rather
than the end.

N - 1

O (log N ) .

For an unsuccessful search, the number of iterations in the loop is
. The reason is that we halve the range in each iteration (rounding
down if the range has an odd number of elements); we add 1 because the final
range encompasses zero elements. For a successful search, the worst case is
iterations because in the worst case we get down to a range of only one
element. The average case is only one iteration better because half of the ele-
ments require the worst case for their search, a quarter of the elements save one
iteration, and only one in

The binary search
is logarithmic
because the search
range is halved in
each iteration.

log N + 1

log N

2 i elements will save i iterations from the worst case.

5. Note that if low and high are large enough, their sum will overflow an int , yielding an incor-
rect negative value for mid. Exercise 5.27 discusses this in more detail.