3
\$\begingroup\$

I created a recursive function that uses binary search to just return true if it finds the value and false if it does not.

I'm new to recursion and binary search so please let me know where I can improve upon.

/**
* Uses binary search O(log n). Returns true if the values is in the value array false if it's not. Recursive
*/
bool binarySearch( int value, int values[], int left, int right ) {
 //keep track of when the array will be empty and return false
 if ( right < left ) {
 return false;
 }
 //Find the middle of the array
 int mid = ( left + right ) / 2;
 //compare the value to the middle of the array. If it's a match return true, else move the left position and right position accordingly
 if( value == values[ mid ] ) {
 return true;
 } else if ( value < values[ mid ] ) {
 right = mid - 1;
 } else {
 left = mid + 1;
 }
 //return the function 
 return binarySearch( value, values, left, right );
}
Vogel612
25.5k7 gold badges59 silver badges141 bronze badges
asked Feb 27, 2017 at 22:59
\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

You return a boolean to indicate whether the value was found or not. The function would be more useful if you returned an index at which the value was found (or -1 if not found). It's better information for the same amount of work.

It appears that left is the leftmost index to consider, and right is the rightmost index to consider. It would be more idiomatic to follow the convention of inclusive-exclusive bounds, with left being the leftmost index and right being just beyond the last element. That way, right - left indicates the number of elements in the array.

You've implemented the search using recursion, but it could also be done using just a loop. You would avoid the overhead of function calls and the possibility of stack overflow.

int mid = ( left + right ) / 2 is vulnerable to integer overflow if both indices are large. int mid = left + (right - left) / 2 would not overflow.

answered Feb 27, 2017 at 23:45
\$\endgroup\$
7
  • \$\begingroup\$ Awesome, thanks for the advice. So on the point of recursion. Is this not a good case to use recursion? I had originally had it in a loop. \$\endgroup\$ Commented Feb 27, 2017 at 23:53
  • \$\begingroup\$ If it can be done in a loop, then generally it should be done in a loop. \$\endgroup\$ Commented Feb 27, 2017 at 23:54
  • 1
    \$\begingroup\$ @200_success: If it can be done in a loop without adding a lot of complexity. Any recursion can be converted to a loop, but in some cases doing so adds a great deal of complexity. \$\endgroup\$ Commented Feb 28, 2017 at 0:20
  • \$\begingroup\$ @JerryCoffin actually that's not strictly true... the recursion that can be converted to loops is called "primitive recursion" ... There's also "higher order" recursion. That's recursive programs that cannot be expressed in loops. The prime example I know of that is the Ackermann-Function \$\endgroup\$ Commented Feb 28, 2017 at 0:28
  • \$\begingroup\$ @Vogel612 One can transform any recursion into loop, but in some cases a stack is required. Anyway, the simplicity of bsearch permits one to use recursion with no fear about overhead. \$\endgroup\$ Commented Feb 28, 2017 at 1:52

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.