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;
}
int array[13] = {1, 2, 3, 5, 7, 9, 11, 13, 17, 19, 23, 27, 29}; bool f = search(23, array, 13);
It incorrectly returnsfalse
. \$\endgroup\$