# 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**- The list must be ordered
- 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**- In all cases, the no. of comparisons in proportional to n
- Hence, no. of comparisons
in binary search is
*O*(log n), where n is the no of items in the list - Obviously binary search is faster then sequential search, but there is an extra overhead in maintaining the list ordered
- For small lists, better to use sequential search
- 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.