[Introduction to Algorithms, CLRS] Exercises 2.3-5

This is a solution for Introduction to Algorithms. I write this for my study purpose.

Exercises 2.3-5

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 v 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, either iterative or recursive, for binary search. Argue that the worst-case running time of binary search is Θ(lg n).

Answer:

BINARY-SEARCH-ITERATIVE(A, v)

1    low = A[1]

2    high = A[A.length]

3    while low <= high 

4        mid = low + (high - low) / 2

5        if A[mid] == v

6            return mid           

7        else if A[mid] > v

8            high = mid - 1

9        else

10          low = mid + 1 

11  return NIL   

BINARY-SEARCH-RECURSIVE(A, v, low, high)

1    if low > high

2        return NIL

3    mid = low + (high - low) / 2 

4    if A[mid] == v

5        return mid

6    else if A[mid] > v           

7        BINARY-SEARCH-RECURSIVE(A, v, low, mid - 1)

8    else       

9        BINARY-SEARCH-RECURSIVE(A, v, low + 1, mid)

Intuitively, the worst case, is when v is absent in A. In this case, we need to search over the whole array to return NIL. So the running time depends on how many times the input size can be divided by 2, i.e. lg n.

And using recurrence formula, we can say running time T(n)=T((n−1)/2)+Θ(1)=Θ(lg n).

source:

https://atekihcan.github.io/CLRS/E02.03-05/