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();
}

1 comments:

Feel free to contact the admin for any suggestions and help.