**Formulate recursive algorithm for binary search.**

*Binary search is quicker than the linear search. However, it cannot be applied to the unsorted data structure. The binary search is based on the approach divide-and-conquer. The binary search starts by testing the data in the middle element of the array. This determines the target is whether in the first half or second half. If the target is in the first half, we do not need to check the second half and if it is in the second half no need to check in first half. Similarly, we repeat this process until we find the target in the list or not found from the list. Here we need 3 variables to identify first, last and middle elements.*

*To implement binary search method, the elements must be in sorted order. Search is performed as follows:*

*a. The key is compared with the item in the middle position of an array*

*b. If the key matches with the item, return it and stop*

*c. If the key is less than mid positioned item, then the item to be found must be in first half of array, otherwise, it must be in second half of array.*

*d. Repeat the procedure for lower (or upper half) of the array until the element is found.*

**Recursive Algorithm for Binary Search:**

*Binary_Search(a,key,lb,ub)*

*begin*

*Step 1: [initialization]*

*lb=0*

*ub=n-1;*

*Step 2: [search for the item]*

*Repeat through step 4 while lower bound(lb) is less than upper bound.*

*Step 3: [obtain the index of middle value]*

*mid = (lb+ub)/2*

*Step 4: [compare to search for item]*

*if(key < a[mid]) then*

*ub=mid-1*

*otherwise if( key > a[mid]) then*

*lb=mid+1;*

*otherwise if(key==a[mid]) Write “match found”*

*return (mid)*

*return Binary_Search(a,key,lb,ub)*

*Step 5: [unsuccessful search]*

*Write “match not found”*

*Step 6: [end of algorithm]*

**Thanks**

**Mukesh Rajput**
## Post A Comment:

## 0 comments:

Thanks

Mukesh Rajput