Complete Binary Search Algorithm
Binary Search Algorithm: ASSUMPTION: • Let a base i 1 ≤ i ≤ n be a list of elements which are sorted in non-decreasing order. PROBLEM: • Consider the problem of determining whether a given element x is present in the list. • In case x is present, we are to determine a value j such that a base j = x. • If x is not in the list then j is to be set to zero. Process of Binary Search Using Divide and Conquer: • Divide-and conquer suggests breaking up any instance • I = (n, a 1 , ... , a n, x) of this search problem into sub instances. • One possibility is to pick an index k and obtain three instances: • I1 = (k - 1, a 1 , ••• , ak-1, x), • I2 = (1, a k , x), and • I3 = (n - k, a k+1 ,••••, an , x). Algorithm of Binary Search: Algorithm Binary Search(a,i,l,x) { if(l=i) then // small(p) only one element { if(x==a[i]) then return i; else return 0; ...