Efficiency of binary search and improvements

Question

Below you can see my binary search method, and as a relatively new programmer I am looking for any suggestions on how it could be improved.

bool found = false;
int min = 0;
int max = 9;
int avg;
int anArray[] = {1,2,3,4,5,6,7,8,9,10};
int userNumber;
printf("Enter a number between 1 and 10:\n");
scanf("%d", &userNumber);
while(!found){
 avg = (min+max)/2;
 if(anArray[avg]==userNumber){
 found = true;
 break;
 }
 if(anArray[avg]<userNumber)
 min = avg+1;
 else if(anArray[avg]>userNumber)
 max = avg-1;
 if( (min==max) && (anArray[max]!=userNumber) )
 break;
}
if(found)
 printf("The number is in index [%d]\n", avg);
else
 printf("Number not found\n");

• Mathieu Guindon: Needs more curly braces! =)
• jacwah: Could you include the whole function, with it's name and parameters? It will be easier to review with more context.
• Matthew Frost: @Mat'sMug whats wrong with the curly braces?

Answer 1

While loop termination

The while loop condition is:

while(!found) {

But when you find your answer, you already do a break. Therefore, the while loop condition could just be:

while (1) {

But there's more. This statement here is not quite right:

if( (min==max) && (anArray[max]!=userNumber) )
 break;

First of all, it is possible that min could actually go beyond max. For example, if originally min is 6, max is 7, and avg is 6, then it could be the case that max becomes 5 afterwards. So you really need to check if min > max and break when that happens.

Secondly, if min == max, there's no need to do an extra equality check and break. You can just loop around one more time.

Putting that all together, I would actually remove that whole if statement and change your while loop to:

while (min <= max) {
 avg = (min+max) / 2;
 if (anArray[avg] == userNumber) {
 found = true;
 break;
 }
 if (anArray[avg] < userNumber)
 min = avg+1;
 else
 max = avg-1;
}

Unnecessary if

Notice I also removed the check for anArray[avg] > userNumber because at that point, it wasn't equal or less than, so it had to be greater than.

• Matthew Frost: Nice solution. I like the elimination of that unnecessary if statement as well, I should have spotted that.