Should the value be updated at the end or at the beginning of while loop?

Question

I was practicing the binary search algorithm and the algorithm gave the same results when the value of mid was updated at the beginning or at the end of the while loop that iterates till start <= end and mid = (start + end)/2 knowing that the value doesn't overflow.

Included header files are:

#include <iostream>
#include <vector>
using namespace std;

The main function is:

int main(){
    vector<int> arr = {1,3,5,6,6,7,8,9,15};
    int size = arr.size();
    int element = 5;

    // binarySearch(vector<int> arr, int size, key)
    int index = binarySearch(arr, size, element);
    cout << element << " found at index " << index << endl;
    return 0;
}

The function code:

key is the element to search for in the vector array arr and size is the number of elements in the array.

    int start = 0, end = size - 1;
    int mid = (start + end)/2;
    while(start <= end){
        // updating the value of mid
        mid = (start + end)/2;
        if(arr[mid] == key){
            return mid;
        }
        else if(key < arr[mid]){
            end = mid - 1;
        }
        else{
            start = mid + 1;
        }
    }
    return -1;
}

The code when mid is updated at the end of while loop is:

int binarySearch(vector<int> arr, int size, int key){
    int start = 0, end = size - 1;
    int mid = (start + end)/2;
    while(start <= end){
        if(arr[mid] == key){
            return mid;
        }
        else if(key < arr[mid]){
            end = mid - 1;
        }
        else{
            start = mid + 1;
        }
        // updating the value of mid
        mid = (start + end)/2;
    }
    return -1;
}

Does updating mid at the end or beginning actually make any difference??

Answer 1

It really doesn't matter where you do it as long as it's calculated before used inside the loop.

• Placing it last in the loop will therefore require a pre-calculation before the loop so you have the same formula in two places. If you can avoid that, it's usually preferable, since you don't want to have to modify the calculation in multiple places in case you need to change it later.

• Placing it first in the loop like you do in the first snippet would for the reason mentioned above be preferable. You can then skip the pre-calculation that you do before the loop and end up with only one.

In the below example, I'm not sending in the size of the vector to the function, since the vector has a size() function that can be used. That function returns a value of type std::size_t so I'll use that type to avoid getting warnings from the compiler about comparing signed variables with unsigned (std::size_t can't hold negative values). That also means that I can't just do size() - 1 since taking the size of an empty vector and subtracting 1 would "wrap around" and become a really huge value. I therefore set end = size() and use while (start < end) in the loop instead (as well as assigning end = mid instead of end = mid - 1 in the loop).

I've also changed the order of the comparisons a bit. If arr holds many values, I'm assuming that the test for equality will be needed very few times so I instead test if key < arr[mid] or arr[mid] < key. If none of those are true, they must be equal.

Example:

constexpr std::size_t not_found = static_cast<std::size_t>(-1);

size_t binarySearch(const std::vector<int>& arr, int key) {
    std::size_t start = 0, end = arr.size();

    while (start < end) {
        std::size_t mid = (start + end) / 2;

        if (key < arr[mid]) {
            end = mid;
        } else if (arr[mid] < key) {
            start = mid + 1;
        } else {
            return mid;
        }
    }
    return not_found;
}

I also added a constant, not_found, which can be used to determine if the value we searched for was found or not. Example usage:

std::size_t index = binarySearch(arr, element);

if(index == not_found) {
    std::cout << element << " was not found\n";
} else {
    std::cout << element << " found at index " << index << '\n';
}