> Does anyone have any ideas on how to do this?
Please read this handy primer:
http://www.catb.org/~esr/faqs/smart-questions.html
What is the purpose of the "found" variable in your original post?
It doesn't seem to be used anywhere, so this pseudocode would appear
to be equivalent:
function binarySearch(a[], lo, hi, x)
while (lo <= hi)
mid = (lo + hi ) / 2
if (a[mid] < x)
lo = mid + 1
else if (a[mid] > x)
hi = mid - 1
else
return mid
end if
end while
return -1
end function binarySearch
Making it recursive would just be a matter of eliminating the while-loop
and instead passing a new search range back into the same function, like so:
function recursiveBinarySearch(a[], lo, hi, x)
if (lo <= hi)
mid = (lo + hi ) / 2
if (a[mid] < x)
return recursiveBinarySearch(a, mid+1, hi, x)
else if (a[mid] > x)
return recursiveBinarySearch(a, lo, mid-1, x)
else
return mid
end if
end if
return -1
end function recursiveBinarySearch