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
Mukesh Rajput

Mukesh Rajput

I am a Computer Engineer, a small amount of the programming tips as it’s my hobby, I love to travel and meet people so little about travel, a fashion lover and love to eat food, I am investing a good time to keep the body fit so little about fitness also..

Post A Comment:

0 comments:

Thanks
Mukesh Rajput