2
\$\begingroup\$

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");
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Needs more curly braces! =) \$\endgroup\$ Jul 8, 2015 at 18:58
  • 2
    \$\begingroup\$ Could you include the whole function, with it's name and parameters? It will be easier to review with more context. \$\endgroup\$
    – jacwah
    Jul 8, 2015 at 19:02
  • \$\begingroup\$ @Mat'sMug whats wrong with the curly braces? \$\endgroup\$ Jul 9, 2015 at 12:21

1 Answer 1

2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Nice solution. I like the elimination of that unnecessary if statement as well, I should have spotted that. \$\endgroup\$ Jul 9, 2015 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.