Implementation of the binary search algorithm [closed]

Question

This is my first implementation the binary search algorithm. I have tested it and so far it is okay. But I need an experienced eye to review the code and recommend best practices.

bool search(int value, int values[], int n) {
  bool x = false;
  int *max;
  int *min;
  int *mid;
  min = values;
  max = min + n - 1;
  mid = min + n / 2;
  while (true) {
    if ((value == *mid || value == *min || value == *max)) {
      x = true;
      break;
    } else if (max - min <= 1) {
      x = false;
      break;
    } else if (value < *mid) {
      n = n / 2;
      mid = min + n / 2;
      max = min + n - 1;
    } else if (value > *mid) {
      n = n / 2;
      mid = max - n / 2;
      min = max - n - 1;
    }
  }

  return x;
}

Answer 1

Variable names

The name x is a very bad name in this case. You should change it to found or something. Even better instead of

x = true;
break;

just do:

return true;

and change the last: return x; to return true;. It is always good to eliminate variables if you can.

Don't modify parameters/arguments

It is confusing when you change the value of the input parameters for example with n = n/2;. This makes the code hard to follow. Instead choose mid as mid = min + (max - min + 1)/2. This makes your intent much clearer.

Avoid while(true) when possible

Some times it is impossible to avoid an infinite loop such as while(true) this is not the case. You should avoid formulating infinite loops like this because it makes it harder to analyze the termination condition of the loop to verify that it will terminate.

while(true)

should be:

while(max - min > 0 )

Simplify branches by realising invariants

Realize that mid is always defined by the min and max variables hence we can define it inside of the loop as a temporary. By doing so and keeping in mind that the array is sorted we can simplify the code as follows:

bool search(int value, int values[], int n) {
  int *min = values;
  int *max = min + n; // Max is exclusive

  while (max - min > 1) {
    int* mid = min + (max - min)/2;
    if(value < *mid){
        max = mid; // Max still exclusive as value < *mid
    }
    else if( value > *mid){
        min = mid;
    }
    else{ // Its not smaller and not larger. Must be equal.
        return true;
    }
  }
  return *min == value;
}