Iterative Binary Search in C++

So yesterday’s post was on how to do a recursive binary search, today is looking at performing the exact same search on an array but doing it iteratively.  So instead of calling a function over and over and over again, we will use a loop. Again, this search is best on a sorted array.

The search function takes in an integer and will return a bool if the integer was found in a given array. The first thing we do is determine the search range, for the first loop, this will be from start of array to the end of array (0 to the size of the array),

Now we jump into the array, we will keep looping as long as the low bound is less than the high. Once the low bound is greater or equal to the high bound, we know that we exhausted the entire loop and did not find our integer in it.

Just like the recursive search, we find our middle first thing inside the loop. From there, we check if our search value is at that middle position. If not, we determine if the value is less than the middle or greater. If it is less than the middle position, we now know that the search value is in between our low bound and the middle and we can adjust our bounds for the next loop accordingly. If our value is greater than the middle, it is in between the middle and our high bound.

We keep adjusting our bounds and narrowing down the search range in this manner until the number is found or the low bound is no longer less than the high.

Happy programing, let me know if you have any questions or improvements!

int sizeOfArray; //contains the size of the search array
int* array; //integer array that we will search through

bool iterativeBinaryFind(int number){
    int highBound = sizeOfArray;
    int lowBound = 0;
    while (lowBound < highBound){
        int middle = (lowBound + highBound)/2;
        
        if (array[middle] == number) return true;
        else if (array[middle] > number) highBound = middle - 1;
        else lowBound = middle + 1;
    }
    return false;
}

Leave a Reply

Your email address will not be published. Required fields are marked *

*

Time limit is exhausted. Please reload the CAPTCHA.

This site uses Akismet to reduce spam. Learn how your comment data is processed.