 In Progress
Lesson 15 of 43
In Progress

# Binary Search

Let ai, 1<= i <= n, be a list of elements that are sorted in non decreasing order. Consider the problem of determining whether a given element x is present in the list.If x is present,we are to determine a value j such that aj = x. If x is not in the list, then j is to be set to zero. Let P = (n,ai,…, al,x) denote an arbitrary instance of this search problem(n is the number of elements in the list ai,…, al is the list of elements,and x is the element searched for)

In this example,any given problem P gets divided (reduced)into one new subproblem. This division takes only theta(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 +l)/2)], then the resulting search algorithm is known as binary search.Note that the answer to the new subproblem is also the answer to the original problem P; there is no need for any combining. Algorithm 2 describes this binary search method, where BinSrch has four inputs a[], i, l and x. It is initially invoked as BinSrch(a,l,n,x).