Binary Search:
We can make binary search recursive like below . first we will see simple binary search then will see recursive binary search.
Simple Binary Search: Note: nElems=number of elements in the array.
public int find(long searchKey)
{
int lowerbound=0;
int uperbound=nElems-1;
int curIn;
while(true)
{
curIn =(lowerbound+uperbound)/2;
if(a[curIn] == searchKey)
return curIn;
else if(lowerbound > uperbound)
return nElems;
else
{
if(a[curIn] < searchKey)
lowerbound =curIn +1;
else
uperbound =curIn-1;
}
}
}
Recursive Binary Search:
public int recFind(long searchKey ,int lowerBound,int upperBound)
{
int curIn;
curIn =(lowerbound+uperbound)/2;
if(a[curIn] == searchKey)
return curIn;
else if(lowerbound > uperbound)
return nElems;
else
{
if(a[curIn] < searchKey)
recFind(searchKey, curIn+1, upperBound);
else
return recFind(searchKey, lowerBound, curIn-1);
}
}