Referring back to the searching problem see Exercise 213 obs

Referring back to the searching problem (see Exercise 2.1-3), observe that if the sequence A is sorted, we can check the midpoint of the sequence against r and eliminate half of the sequence from further consideration. The binary search algorithm repeats this procedure, halving the size of the remaining portion of the sequence each time. Write pseudocode, cither iterative or recursive, for binary search. Argue that the worst-case running time of binary search is Phi(lg n).

Solution

Iterative approach:

Let A be a sorted array

n: size of array

x: value to be searched

we have, low=1

high=n

while x is not found:

if high < low

       then element does not exist

      let mid=(high+low) / 2

if A[mid]<x

       then low=mid+1

if A[mid] > x

       then high=mid-1

if A[mid]==x

       then return mid //element has been found

Worst case running time:

In the best case, element to be searched is present in the middle.

But in worst case, we need to divide the array into two halfs everytime element is not in the middle.

For example, if we have 1024 elements, we first find the element at 512th position
If it is not present, then we visit either of the two halfs and discards another one.

We continue this process until the element is found

Hence, for worst case, if we have 1024 elements, we will split the array as: 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2
Hence, lg(n) is the worst case running time