Friday, 1 December 2017

Formulate recursive algorithm for binary search.

Binary search is quicker than the linear search. However, it cannot be applied on 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 target is whether in the first half or second half. If target is in first half, we do not need to check the second half and if it is in second half no need to check in first half. Similarly we repeat this process until we find 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 item in the middle position of an array
b. If the key matches with 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 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

No comments:

Post a Comment

Thanks
Mukesh Rajput