Monday, June 19, 2017

Algorithm for recursive binary search

Algorithm BinarySearch(a, i, 1,x).

//Given an array  a(i,l) of elements in non-decreasing.
//order, 1<=i<=1, determine whether x is present and
//if so, return j such that x = a[j], else return 0.

{

if(1=i)then
{
if(x=a[i]) then return i;
else return 0;
}
else
{
mid:=[(i+1)/2];
if(x=a[mid]) then return mid;
else if(x<a[mid]) then
return Binarysearch(a, i, mid-1, x);
else return Binarysearch(a, mid+1, 1, x);
}
}