Analysis of Algorithms : An Active Learning Approach

2.2 BINARY SEARCH 51

Now, let’s consider the second situation where we include the possibility
that the target is not in the list of elements. We still have N possibilities for the
target being in the list, but now we have to add in the N + 1 possibilities that
the target is not in the list. There are N + 1 of these possibilities because the
target can be smaller than the element in location 1, larger than the element in
location 1 but smaller than the one in location 2, larger than the element in
location 2 but smaller than the one in location 3, and so on, through the possi-
bility that the target is larger than the element in location N. In each of these
cases, it takes k comparisons to learn that the target is not in the list. There are
now 2 *N + 1 possibilities to include in our calculation. Putting all of this
together, we get

By a simiar series of substitutions as above, we get

This is just a little larger than the average case for when the key is known to be
in the list. So, if the list has 1,048,575 (2^20
1) elements, the first average case
is about 19 and the second is 19.5.

AN() 2 ----------------N^1 + 1 - i 2 i-1

i=1

k

∑







==+()N+ 1 k forN 2 k– 1

AN() ()k–^12

[]k+ 1 +()N+ 1 k

2 N+ 1

= ----------------------------------------------------------------

AN() ()k–^12

[]k+ 1 +() 2 k– 1 + 1 k

22 ()k– 1 + 1

= -------------------------------------------------------------------------

AN() k^2

()k– 2 k+ 1 + 2 kk

2 k+1– 1

= ------------------------------------------------

AN() k^2

k+1– 2 k+ 1

2 k+1– 1

= ----------------------------------

AN()k^2

k+1– 2 k+ 1

2 k+1

≈----------------------------------

AN()≈k–^12 -- ==lg()N+ 1 – -- 21 forN 2 k– 1