Explain in detail about binary search algorithm.

Introduction

Binary search is an extremely efficient algorithm. This search technique searches the given item in minimum possible comparisons. To do the binary search, first we have to sort the array elements. The logic behind this technique is given below.

1.                                                                           First find the middle element of the array.

2.         Compare the middle element with an item.

3.         There are three cases.

a). If it is a desired element then search is successful,

b). If it is less than the desired item then search only in the first half of the array.

c). If it is greater than the desired item, search in the second half of the array.

4. Repeat the same steps until an element is found or search area is exhausted.

In this way, at each step we reduce the length of the list to be searched by half.

Requirements

1. The list must be ordered
2. Rapid random access is required, so we cannot use binary search for a linked list

Algorithm

Let 'a’ be the array of size 'Maxsize' and 'LB', 'UB' and 'mid' are variables to denote first, last and middle location of a segment. This algorithm finds the location 'Loc' of 'item' in array 'a’ or return fail(sets loc=NULL).

1.     [Initialize segment variables]

set beg = LB, end = UB and mid = int((beg + end)/2)

2.     Repeat steps 3 and 4 while beg<=end and a[mid]!=item

3.     if item<a[mid],then

set end=mid – 1

Else

set beg=mid + 1

[End if]

4.     set mid=int((beg + end)/2)

5      if a[mid]=item then

set loc=mid

print the value and its position

else

set loc=NULL

print search unsuccessful

[End if]

6.     Exit

Binary search efficiency

1. In all cases, the no. of comparisons in proportional to n
2. Hence, no. of comparisons in binary search is O (log n), where n is the no of items in the list
3. Obviously binary search is faster then sequential search, but there is an extra overhead in maintaining the list ordered
4. For small lists, better to use sequential search
5. Binary search is best suited for lists that are constructed and sorted once, and then repeatedly searched

Binary Search Procedure

void binsrch( int a[], int beg, int end, int item)

{

int mid;

int count = 0;

mid = (beg + end)/2;

while(beg <= end && item != a[mid])

{

If(item < a[mid])

end = mid - 1;

else

beg = mid + 1;

mid = (beg + end)/2;

count ++;

}

if(item == a[mid])

{

printf(“\nSearch Successful!!!\n It took %d iterations to find this item”, cnt);

         printf(“\nThe position is %d”,mid);

}

else

printf(“\n Search Unsuccessful”);

getch();

}