Implementing Binary Search in C

Question

Quick question here about implementing binary search :-). This is the function I have now, I haven't quite figured out the logic for passing the correct number for i. However, when I debugged this function, I found that when value = values[i] (match), unintended behavior occurred.

My intention was for true to be returned, thus triggering a match and exiting the function. Actual behavior result in return true; and followed by return false; (incorrectly). Does anyone know how to ensure return true; exits the function? Or tips to guide me towards my mistake? Thanks so much!

bool search(int value, int values[], int n){

   int i = ((n - 1) / 2); 

   if(value == values[i])
   {
      return true;
   }
   else if(value < values[i])
   {
      n = i;
      search(value, values, n);
   }
   else if(value > values[i])
   {
      n = (i * 1.5);
      search(value, values, n);
   } 
   return false; 
}

True is returned. The caller then ignores the true and returns false. The caller of that then ignores the false and returns false. And so on, back up to the top level. — Stack Exchange Broke The Law
– Stack Exchange Broke The Law, Commented Nov 20, 2015 at 22:16

R Sahu · Accepted Answer · 2015-11-21 05:32:03Z

4

You are missing couple of return keywords.

search(value, values, n);

should be:

return search(value, values, n);

There are two such lines.

Without those return keywords, the function always goes to the end and returns false.

Update, in response to OP's comment

Your function does not have any checks to ensure that values is not accessed out of bounds. I think it will never try to access anything with a negative index but it has the chance to access elements with an index that is higher than the allowed index values. I suggest changing the function to use:

int search(int value, int values[], int start, int end)
{
   if ( start >= end )
   {
      return 0;
   }

   int mid = (start + end)/2; 

   if(value < values[mid])
   {
      return search(value, values, start, mid);
   }
   else if(value > values[mid])
   {
      return search(value, values, mid+1, end);
   } 
   else
   {
      return (value == values[mid]);
   }
}

and call it with right start and end values when calling from outside the function.

int values[] = {1, 4, 6, 8};
bool found = search(2, values, 0, sizeof(values));

edited Nov 21, 2015 at 5:32

answered Nov 20, 2015 at 21:42

R Sahu

207k15 gold badges168 silver badges291 bronze badges

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

2 Comments

patchybear Over a year ago

Thanks @r-sahu! That fixed the function within debugging and returned a correct find. When I tested it in our larger assignment program, it caused a segmentation fault. Are there any critical issues within my implementation which would have caused this?

David C. Rankin Over a year ago

Most likely, if you used the answer in a larger application it is still calling the function with bool search(int value, int values[], int n) instead of bool search(int value, int values[], int start, int end) where search is called.

lrleon · Accepted Answer · 2015-11-20 23:58:12Z

Let me comment that it is possible to write an effective version of your function with exactly your interface. Something like:

bool search(int value, int values[], int n)
{
  if (n == 0) // searching in an empty set?
    return false;

  int i = (n - 1) / 2;

  if (value == values[i]) // the middle contains value?
    return true;
  else if (value < values[i]) // would be value to the left of i
    return search(value, values, i);
   else // so it would be to the right; no need of if (value > values[i])
     return search(value, values + i + 1, n - i - 1);
}

This function, which has the same signature that yours, reduce the searching range through the number of elements n and the base of array pointer. When the search is performed to the left of center, the numbers of elements decrease to i and when the search is performed to the right the array base address if increased by i + 1 and the number of elements is decreased by i + 1.

Note that your third if is not necessary; if it is reached, then the predicate always will be true, because value is not equal neither less than value[i], so it is greater.

Collectives™ on Stack Overflow

Implementing Binary Search in C

2 Answers 2

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related