My Profile
Active Members
TodayLast 7 Days
more...
Awards & Gifts
Online Exams
Fresher Jobs
Our fresher job section is exclusively for fresh graduates! Find jobs for freshers in major Indian
cities including Bangalore, Chennai, Hyderabad, Pune or Kochi
Resources
Find educational articles, blogs, discussion threads and other resources.
Colleges
Find details about any college in India or search for courses.
Paid Surveys
|
Recursive Binary Search
Posted Date: 15 Feb 2008 Resource Type: Articles/Knowledge Sharing Category: General
|
Posted By: rajasekhar Member Level: Gold
Rating:  Points: 4
|
|
|
Recursive Binary Search
Iterative algorithms, ie those with a loop, can usually be easily rewritten to use recursive function calls instead of loops. This is almost always a bad idea because the iterative version is usually simpler, faster, and uses less memory.
Some problems, eg traversing a tree, are better solved recursively because the recursive solution is so clear (see Binary Tree Traversal). Binary search is really is better in the non-recursive form, but it is one of the more plausible algorithms to use as an illustration of recursion.
This recursive version checks to see if we're at the key (in which case it can return), otherwise it calls itself so solve a smaller problem, ie, either the upper or lower half of the array.
Example
int rBinarySearch(int sortedArray[], int first, int last, int key) {
// function:
// Searches sortedArray[first]..sortedArray[last] for key.
// returns: index of the matching element if it finds key,
// otherwise -(index where it could be inserted)-1.
// parameters:
// sortedArray in array of sorted (ascending) values.
// first, last in lower and upper subscript bounds
// key in value to search for.
// returns:
// index of key, or -insertion_position -1
// if key is not in the array.
if (first <= last) {
int mid = (first + last) / 2; // compute mid point.
if (key == sortedArray[mid])
return mid; // found it.
else if (key < sortedArray[mid])
// Call ourself for the lower part of the array
return rBinarySearch(sortedArray, first, mid-1, key);
else
// Call ourself for the upper part of the array
return rBinarySearch(sortedArray, mid+1, last, key);
}
return -(first + 1); // failed to find key
}
|
Responses
|
No responses found. Be the first to respond and make money from revenue sharing program.
|
|
|