Java Reference
In-Depth Information
That is, beginning with
n
items, we would be left with
n
/
2 items, then
n
/
4 items, and so on. In the
worst case, the search would continue until only one item was left. That is,
n
/
2
k
would equal 1 for
some integer value of
k
. This value of
k
gives us the number of times the array is divided in half, or
the number of recursive calls to
binarySearch
.
If
n
is a power of 2,
n
is 2
k
for some positive
k
. By the definition of a logarithm,
k
is log
2
n
.
If
n
is not a power of 2, you can find a positive integer
k
so that
n
lies between 2
k
- 1
and 2
k
. For
example, if
n
is 14, 2
3
<
14
<
2
4
. Thus, we have for some
k
≥
1,
2
k
- 1
<
n
<
2
k
k
-
1
<
log
2
n
<
k
k
=
1
+
log
2
n
rounded down
=
log
2
n
rounded up
To summarize,
k
=
log
2
n
when
n
is a power of 2
k
=
log
n
when
n
is not a power of 2
2
In general,
k
—the number of recursive calls to
binarySearch
—is
log
n
.
2
Note:
Ceiling and floors
The
ceiling
of a number
x
, denoted as , is the smallest integer greater than or equal to
x
.
For example, is 5. The
floor
of a number
x
, denoted as
,
is the largest integer less
than or equal to
x
. For example, is 4. When you
truncate
a positive real number to an
integer, you actually are computing the number's floor by discarding any fractional portion.
x
4.1
x
4.9
Each call to
binarySearch
, with the possible exception of the last one, makes two comparisons
between the target and the middle element in the array: One tests for equality and one for less than
or greater than. Thus, the binary search performs at most 2
log
n
comparisons, and so in the
2
worst case is O(log
n
).
To search an array of 1000 elements, the binary search will compare the target to about 10 array
entries in the worst case. In contrast, a simple sequential search could compare the target to as
many as all 1000 array entries, and on average will compare it to about 500 array elements.
Note:
The time efficiency of a binary search of an array
Best case: O(1)
Wor st ca se: O(log
n
)
Average case: O(log
n
)
Question 9
Think of a number between 1 and 1 million. When I guess at your number, tell
me whether my guess is correct, too high, or too low. At most, how many attempts will I
need before I guess correctly?
Hint
: You are counting guesses, not comparisons.
