why doesn't my implementation to binary search correctly handle not finding an element?

Question

I was practicing to write the code for binary search after watching its short, before starting on pset3.

The code that I wrote asks for the length of array, then sorts it and asks for the number to be searched for. the following code is working, if the number is there in the list, but not if it's not.

can anyone one explain why? following is the code where key is the number to be searched for in the array data of size length:

int midpoint = (length - 1) / 2;
int min = 0;
int max = length - 1;

while(true)
{
    if(data[midpoint] > key)
    {
        max = midpoint - 1;
        midpoint =(min + max) / 2;
    }
    else if(data[midpoint] < key)
    {
        min = midpoint + 1;
        midpoint = (min + max)/2;
    }
    else if(data[midpoint] == key)
    {
        printf("the number %i is in the list.\n", key);
        break;
    }
    else
    {
        printf("The number is not in the list.\n");
        break;
    }
}

Answer 1

here are my takes on the code:

• you are duplicating some stuff. for example, why calculating length - 1 twice? instead, you could start with defining min and max.

• you don't really need midpoint to be defined outside the loop. also, instead of repeating the calculation of midpoint inside the loop, you could calculate it once at the beginning of each iteration.

• logically, there are only three possible cases:

  1. either data[midpoint] > key.
  2. or data[midpoint] < key.
  3. else (aka data[midpoint] == key).

  
  there is no fourth case. as a result, your loop shouldn't iterate until it hits a break, when it finds the element, because it may never find it.

  instead, it should stop when there are no more halves to look into/throw away (hint: can be determined in terms of min and max).

• where to handle the case that the element is not found? definitely not inside that loop here.