Writing a recursive binary search in C

Question

I've found the following code online,

int binary_search(int a[], int low, int high, int target) {
    if (high < low)
        return -1;
    int middle = (low + high)/2;
    if (target < a[middle])
        return binary_search(a, low, middle-1, target);
    else if (target > a[middle])
        return binary_search(a, middle+1, high, target);
    else if (target == a[middle])
        return middle;
}

My function has a specified prototype(meaning that it has a set number of arguments that cannot be altered) this is what I have so far

bool search(int value, int array[], int n) {
    if (array[n/2] == value)
        return 1; 
    else if (array[n/2] < value)
        return search(value, &array[n/2], (n)/2);
    else
        // how do I "return" the other half?
}

Does my implementation look correct so far? I can't seem to figure out how to implement the final else statement.

The "High" and "Low" are basically markers in the array that is passed. They are the section to look through. So basically the initialization would be high = size of array, low = 0; — Nicholas
– Nicholas, Commented Jul 23, 2011 at 23:30
What's your question, exactly? You seem to have no trouble with dealing with the other half of the array. — In silico
– In silico, Commented Jul 23, 2011 at 23:30
i don't know why the first code block came out really messy. It has the right formatting in my editor box. sorry — user859753
– user859753, Commented Jul 23, 2011 at 23:30
@user859753: For code, you use the code block button (the one that looks like { }), not the quote button (the one that looks like “). — In silico
– In silico, Commented Jul 23, 2011 at 23:32
my question is how do I implement the other half (after the else statement) thanks! — user859753
– user859753, Commented Jul 23, 2011 at 23:34

Manlio · Accepted Answer · 2011-07-23 23:36:46Z

2

high and low represent the bounds of subarray in which continue the research. If you analyze the code you'll notice that if target is smaller that a[middle] you'll have to continue the research in the first half of the array (in fact it calls binary_search passing the same low bound but, as a superior bound, the actual middle-1). On the other side, if target is greater that a[middle] you'll have to continue the research in the second half of the array (from middle+1 to high). Of course, if target is equal to a[middle] you've finished.

edited Jul 23, 2011 at 23:36

answered Jul 23, 2011 at 23:30

Manlio

10.9k9 gold badges55 silver badges81 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user859753 Over a year ago

but my function's parameters have been restricted two three(array, value(target), n (array size) ). How can i implement a solution without the "high" and "low" parameters?

Manlio Over a year ago

On the fly you can try else { return search(value, array, n/2); }. You should do additional checks if n is not a power of 2. Besides, you are considering also middle value (that you already checked), so it'd be better to start from array[n/2 + 1] if it's greater, otherwise consider a subarray from 0 to n/2 -1.

Edwin Buck · Accepted Answer · 2011-07-24 03:09:20Z

The trick to writing a recursive anything:

Figure out how it should end.
Figure out how it should look one step before it ends.
Figure out how it should look two steps before it ends, and how moving from #2 to #1 is exactly the same as moving from #3 to #2.

Step #1:

If the number at the beginning of the search range is the desired number, return true.

If the end of the search range is the same as the beginning of the search range, and the number in the search range is not the desired number, return false.

Step #2:

If the search range has a length of two, split it into two one element search ranges, and search the range that might contain the required number.

Step #3:

If the search range has a length of more than two, split it into two roughly equal search ranges, and search the range that might contain the required number.

(which combining the two would look like)

If the search range has a length of two or more elements, split it into two roughly equal ranges, check the highest (last) number in the "lower" range, if the number is equal to or less than that number, search the lower range; otherwise, search the higher range.

This technique will not return you an optimum solution unless you select an optimum way to solve the problem; however, it will return you a correct solution (provided you do not make any true blunders).

Now the code

bool search(int value int array[], int lowIndex, int highIndex) {
  if (array[lowIndex] == value) {
    return true;
  } else if (lowIndex == highIndex) {
    return false;
  }
  int middleIndex = lowIndex + highIndex / 2;
  if (array[middleIndex] <= value) {
     return search(value, array, lowIndex, middleIndex);
  } else {
     return search(value, array, middleIndex+1, highIndex);
  }
}

When reading code online, you have a big disadvantage. You don't do any of the above three steps, so you really have to go about solving the problem backwards. It is akin to saying, I have a solution, but now I have to figure out how someone else solved it (assuming that they didn't make any mistakes, and assuming that they had the exact same requirements as you).

Rudy Velthuis · Accepted Answer · 2011-07-23 23:34:40Z

0

The high and low variables represent the current range you are searching. You usually start with the beginning and end of the array, and then determine if the value is in the first or second half, or exactly in the middle. If it is in the middle, you return that point. If it is below the middle, you search again (recursively), but now only in the lower half. If it is above the middle, you search the upper half. And you repeat this, each time dividing up and narrowing the range. If you find the value, you return, otherwise, if the range is so narrow that it is empty (both low and end high indexes are the same), you didn't find it.

answered Jul 23, 2011 at 23:34

Rudy Velthuis

28.9k5 gold badges50 silver badges97 bronze badges

Comments

Patrick87 · Accepted Answer · 2011-07-23 23:37:37Z

0

High and low are upper and lower bounds on the candidate indices of the array. In other words, they define the portion of the subarray in which it is possible for the search target to exist. Since the size of the subarray is cut in half each iteration, it is easy to see that the algorithm is O(log n).

answered Jul 23, 2011 at 23:37

Patrick87

28.4k3 gold badges41 silver badges75 bronze badges

Comments

dougallj · Accepted Answer · 2011-07-24 02:32:23Z

0

return search(value, &array[(n)/2], (n)/2);

On your current code, first of all, n should not be in parentheses (it doesn't make a difference, but it confuses me).

Next up, if it's meant to be returning the index in the array, your code doesn't do that, it returns 1. Judging by the prototype, you might consider a non-recursive approach, but this can work fine if you add the right values on to each return.

You can figure out the other statement. Just draw a picture, figure out where the pointers should be, and code them up. Here's a start:

       new array if > n/2
         v-----------v
0, 1, 2, 3, 4, 5, 6, 7
         ^
        n/2

Actually, you probably don't want to be including your middle value. Finally, make sure to take in to account lists of length zero, one, two and three. And please write unit tests. This is probably one of the most often incorrectly implemented algorithms.

answered Jul 24, 2011 at 2:32

dougallj

4292 silver badges5 bronze badges

2 Comments

user859753 Over a year ago

I've made the change to (n). the function returns a 1 because the function is in boolean, so in effect, the function tells the caller whether The number's been found. The problem specifically asked for a recursive solution, but hints the possibility of creating another function that search may call

dougallj Over a year ago

In that case, it might be easier to make another recursive function with the int begin, int end arguments (high and low, as above). Either way, think about the conditions under which you'll be returning zero.

TheCodeArtist · Accepted Answer · 2012-10-20 03:27:17Z

0

I have tried to resolve your problem and this below code is really work . But what is the condition to escape recursion if value that want to be searched not lies in array

if(value==a[size/2]) return size/2;

    if( value<a[size/2]) {
        search(a,size/2,value);
    } else if (value>a[size/2] && a[size/2]<a[(a.length-1)/2]) {
        search(a,size/2+size,value);
    } else {
        search(a,size/2+a.length-1,value);
    }

edited Oct 20, 2012 at 3:27

TheCodeArtist

22.6k4 gold badges74 silver badges135 bronze badges

answered May 12, 2012 at 2:21

Hakun Nguyen

1

Comments

slavoo · Accepted Answer · 2013-12-14 19:11:24Z

0

int * binSearch (int *arr,int size, int num2Search)
{

    if(size==1)
        return ((*arr==num2Search)?(arr):(NULL));

    if(*(arr+(size/2))<num2Search)
        return binSearch(arr+(size/2)+1,(size/2),num2Search);

    if(*(arr+(size/2))==num2Search)
        return (arr+(size/2));

    return binSearch(arr,(size/2),num2Search);
}

edited Dec 14, 2013 at 19:11

slavoo

6,11464 gold badges40 silver badges41 bronze badges

answered Dec 14, 2013 at 18:48

user3102756

1

Collectives™ on Stack Overflow

Writing a recursive binary search in C

7 Answers 7

2 Comments

Comments

Comments

Comments

2 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

7 Answers 7

2 Comments

Comments

Comments

Comments

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related