VietMX Staff asked 3 years ago
- The first difference is that the while loop from iterative approach is replaced by a recursive call back to the same method with the new values of
lowandhighpassed to the next recursive invocation along withArrayandkeyor target element. - The second difference is that instead of returning false when the while loop exits in the iterative version, in case of the recursive version, the condition of
low > highis checked at the beginning of the next level of recursion and acts as the boundary condition for stopping further recursive calls by returning false. - Also, note that the recursive invocations of
binarySearch()return back the search result up the recursive call stack so that true or false return value is passed back up the call stack without any further processing. - To further optimize the solution, in term of running time, we could consider implement the tail-recursive solution, where the stack trace of the algorithm would not pile up, which leads to a less memory footprint during the running time. To have the tail-recursive solution, the trick is to simply return the result from the next recursive function instead of further processing.
Implementation
function binarySearch(sortedArray, searchValue, minIndex, maxIndex) {
var currentIndex;
var currentElement;
while (minIndex <= maxIndex) {
// Find the value of the middle of the array
var middleIndex = (minIndex + maxIndex) / 2 | 0;
currentElement = sortedArray[middleIndex];
// It's the same as the value in the middle - we can return!
if (currentElement === searchValue)
{
return middleIndex;
}
// Is the value less than the value in the middle of the array
if (currentElement < searchValue) {
return binarySearch(sortedArray, searchValue, middleIndex + 1, maxIndex);
}
// Is the value greater than the value in the middle of the array
if (currentElement > searchValue) {
return binarySearch(sortedArray, searchValue, minIndex, middleIndex - 1);
}
}
return -1;
}