My first Codeforces blog post! Hooray!

This post was inspired by the problem: E. Iva & Pav of Codeforces round 900 (https://codeforces.me/contest/1878/problem/E). This problem requires us to find the last element in the array such that the Bitwise AND values of all elements starting from the query index are greater than or equal to key value. The important takeaway of this problem is that the Bitwise AND value can only decrease after including another element. This permits us to use Binary Search, which brings us to our topic.

The Problem

Unfortunately being the newbie that I am, I tried applying basic binary search, lower bound and upper bound but didn't succeed. Here we are required to find the last element which satisfies the given condition thus requiring a slightly different binary search algorithm. This sparked my urge to dive deep into the bowel of Binary Search.

The Solution

So After years (about 0.01 years) of painstaking research I finally compiled a list of five algorithms that will satisfy most problems regarding binary search. It also lead to better my understanding of the binary search algorithm.

So the main difference between these algorithms is whether they return the first element or last element satisfying required condition. To illustrate their outputs, consider an array, Ex- [1, 1, 1, 2, 2, 3, 4, 4, 4, 7, 7, 9] key = 4 In this array basic binary search algorithm wont work as there are repeating values. If you use lower bound or upper bound algorithm, it will output the first element satisfying the condition (lets say >= or > key respectively) which is index 6 and 9 respectively. But we could require the last element that is equal to key i.e at index 8. This leads us to five different algorithms.

The Algorithms

These are the five algorithms for ascending order and they all have their descending order counterparts as well.

int l = 0;
int r = n-1;
int result = -1;
int mid;

while(l <= r)
{
    mid = (l+r)/2;

    if(arr[mid] == key)
    {
        result = mid;
        break;
    }
    else if(arr[mid] < key)
    {
        l = mid+1;
    }
    else
    {
        r = mid-1;
    }
}

int l = 0;
int r = n-1;
int result = -1;
int mid;

while(l <= r)
{
    mid = (l+r)/2;

    if(arr[mid] >= key)
    {
        result = mid;
        r = mid-1;
    }
    else
    {
        l = mid+1;
    }
}

int l = 0;
int r = n-1;
int result = -1;
int mid;

while(l <= r)
{
    mid = (l+r)/2;

    if(arr[mid] > key)
    {
        result = mid;
        r = mid-1;
    }
    else
    {
        l = mid+1;
    }
}

int l = 0;
int r = n-1;
int result = -1;
int mid;

while(l <= r)
{
    mid = (l+r)/2;

    if(arr[mid] <= key)
    {
        result = mid;
        l = mid+1;
    }
    else
    {
        r = mid-1;
    }
}

int l = 0;
int r = n-1;
int result = -1;
int mid;

while(l <= r)
{
    mid = (l+r)/2;

    if(arr[mid] < key)
    {
        result = mid;
        l = mid+1;
    }
    else
    {
        r = mid-1;
    }
}