I am learning in C about sorting arrays and while loops. Some code from the book I'm using to study this with is the following:

//function to perform binary search of an array
size_t binarySearch(const int b[], int searchKey, size_t low, size_t high)
{
    //loop until low index is greater than high index
    while (low <= high) {
        
        //determine middle element of subarray being searched
        size_t middle = (low   high) / 2;

        //display subarray used in this iteration
        printRow(b, low, middle, high);

        // if searchKey matched middle element, return middle
        if (searchKey == b[middle]) {
             return middle;
        }

        // if searchKey is less than middle element, set new high
        else if (searchKey < b[middle]) {
           high = middle - 1; //search low end of array
        }

        else {
           low = middle   1; //search high end of the array
        }
     }//end while

     return -1; //searchKey not found
}
         

The problem is that I can't figure out how the initial while condition works: while (low <= high). I mean it seems like low can never be greater than high. Can anyone tell me under what situation low would be greater than high and therefore terminate the loop?

I tried to write down and visualize how the algorithm might work, but I cannot understand it.

CodePudding user response：

In these conditions value of low is greater than the value of high

When an element is not in the list and the element to find is greater than the element at mid: There will be only one element in the list, so the low = middle 1 will execute, and the resulting value of low greater

When in function call we pass high greater than low

binarySearch(arr, search_value, 4, 3)

Try for these inputs

Input

array = {2, 3, 4, 10, 40}
to_search = 11

Output (low, high)

0, 4
3, 4
4, 4
4, 3  <--- low > high

CodePudding user response：

Well, don't treat the statement as something in normal everyday talks. Of course, normally there is no discussion about any chance of having 5 being higher, than, say, 8.

But in code, loops and conditions, things are different, because code is dynamic. If you'll follow the code, among the many conditions you'll see that there is a situation of low = middle 1; (that's the last condition). At the "opposite" spectrum you'll see a condition above it high = middle - 1;. And of course one that controls middle: middle = (low high) / 2;.

In this situation, low has a chance (assuming you hit its condition) to increase and high has a chance (again, assuming you hit its condition) to decrease.

Going back to our random example at the start of 5 and 8, that means the first number might eventually go up from to 7 and 8 might go down to 4. In our code, of course, you need to follow the actual flow and see the values and how and when they hit those conditions.

But bottom line is, low and high are never static. This is a rare occasion as you'll find most loops only modifying the first variable (in our case **low **). But that is how one patter of loops is: you start off at one value or one condition, then you progress in the code until you break that condition.

Small caveat: because control flow is man-made, if one does not pay attention they might end up with infinite loops (meaning the stop condition is never triggered). That means the program will go in a loop and basically "sit still" but still use up CPU power (and, depending on what it does in the loop, even memory until the machine runs out of memory).

What you'll see in some loops as a precaution is something like this:

int i = 0;
while (some condition)
{
    if (i   > some number)
        break;

    ... some control flow code
}

What that does is a failsafe stop. a variable is incremented each loop until a number that the programmer feels is safe enough then exists the loop. break is how you exit loops. Of course, this is just a failsafe, as I said, normally you need to make sure that the code inside the loops are properly handled and no chance of an infinite loop happens.

CodePudding user response：

Let's assume that searchKey is not in your array to make the explanation easier. Here is an example:

• b is { 1, 2, 3 }
• searchKey is 4
• low is 0
• high is 2

Initially low is less than high so we enter the while loop. middle is (0 2) / 2 which is 1. In our particular case we hit the else statement which means we set low to middle 1 which is 2. That means low is now equal to high so the loop continues. This time middle is (2 2) / 2 which is 2. We hit the else statement again setting low to 3 making low greater than high and ending the loop

If instead searchKey was -1 then we would have set high to middle - 1 which is 0. That would have meant high is now equal to low. On the following iteration of the loop we would set high again with a value of -1 ending the loop

CodePudding user response：

When low > high, this means that the list does not contain the searchKey.