BINARY SEARCH

Divide-and-conquer can be used to solve this problem. Let Small(P) be
true if n = 1. In this case, S(P) will take the value i if x = ai; otherwise it
will take the value 0. Then g(l) = ? (1). If P has more than one element, it
can be divided (or reduced) into a new subproblem as follows. Pick an index
q (in tho range [i, l]) and compare x with aq . There are three possibilities:
(1) x = aq: In this case the problem P is immediately solved.
(2) x < aq: In this case x has to be searched for only in the sublist ai, ai+1, ... , aq-l .
Therefore, P reduces to (q - i, ai, ... ,aq-l, x).
(3) x > aq: In this case the sublist to be searched is aq+l, ... ,al. P reduces to (l - q, aq+1, ... ,al, x).
In this example, any given problem P gets divided (reduced) into one
new subproblem. This division takes only ? (1) time. After a comparison
with aq , the instance remaining to be solved (if any) can be solved
by using this divide-and-conquer scheme again. If q is always chosen such
that aq is the middle element (that is, q = (n + 1)/2), then the resulting
search algorithm is known as binary search. Note that the answer to
the now subproblem is also the answer to the original problem P; there
is no need for any combining. The algorithm describes this binary search
method, where BinSrch has four inputs a[ ], i, 1, and x. It is initially invoked
as BinSrch(a, 1, n, x).