Binary Search Variations Application

#	User	Rating
1	Benq	3857
2	jiangly	3810
3	maroonrk	3534
4	tourist	3528
5	Kevin114514	3510
6	turmax	3411
7	Um_nik	3387
8	Radewoosh	3367
9	heuristica	3322
10	strapple	3317

#	User	Contrib.
1	Qingyu	157
2	maspy	150
3	Um_nik	145
4	Errichto	139
5	adamant	136
6	maroonrk	134
7	DNR	133
8	Dominater069	129
8	AmShZ	129
8	BledDest	129

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).

Introduction

Most of you already know about binary search, what to use it for and its basic algorithm. This is not what I want to show here as it has already been done by more qualified people. I want to list all the slightly different binary search algorithms so that we can understand where to apply each of them.

The Problem

For this problem 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. Unfortunately I was not able to find a comprehensive list of binary search algorithms. So After years (about 0.01 years) of painstaking research I finally found five algorithms that will satisfy most problems regarding binary search.

The Algorithms

The Basic Binary search algorithm only applies for arrays with distinct elements. If the array has multiple instances of one element we need to apply a different algorithm. For example you could need any of the following elements for your specific problem.

Ex- [1, 2, 3, 5, 6, 8, 9, 10] key = 5 Ex- [1, 1, 1, 2, 2, 3, 4, 4, 4, 7, 7, 9] key = 4

These are the five algorithms for ascending order respectively in the order of the index of required element in array:

Binary Search for strictly increasing Array (Basic Binary Search)

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

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

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

Binary Search for Last element < Key

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

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

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

Binary Search Lower Bound (First Element >= Key)

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

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

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

Binary Search for Last element <= Key

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

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

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

Binary Search Upper Bound (First Element > Key)

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

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

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

Their corresponding decreasing array counterparts:

Binary Search for strictly decreasing Array (Basic Binary Search)

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

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

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

Binary Search Last Element > Key

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

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

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

Binary Search Lower Bound (First Element <= Key)

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

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

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

Binary Search Last Element >= Key

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

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

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

Binary Search Upper Bound (First Element < Key)

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

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

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

Important Takeaways

The main point we can gleam from these algorithms is that when you get an element that satisfies the given condition, you immediately set result = mid. Although quite obvious some algorithms I read don't set a different variable for result and only take the value of mid after the loop ends as the answer which can be fail sometimes. Another important point to note is that the pointer we move (l or r) depends on whether we want the first element or the last element, not whether the array is ascending or descending. If we want the first element we set r = mid-1 and for last element we set l = mid+1 when we get required condition.

Hopefully this Blog can help someone ^~^!

Note

My problem requires use of 4th algorithm from descending set.

Rev.	By	When	Δ	Comment
en15	Supersidd	2024-07-11 16:18:19	0	(published)
en14	Supersidd	2024-07-11 15:58:06	2	Tiny change: ' key = 5\nEx- [1, ' -> ' key = 5\n\nEx- [1, '
en13	Supersidd	2024-07-11 15:56:57	14
en12	Supersidd	2024-07-11 15:56:03	178
en11	Supersidd	2024-07-11 15:49:47	636
en10	Supersidd	2024-07-11 15:36:46	1125
en9	Supersidd	2024-07-11 15:17:29	16
en8	Supersidd	2024-07-11 15:15:02	1858	Tiny change: 'oiler>\n\n ' -> 'oiler>\n\n<spoiler summary="">\n```c++\n\n```\n<\spoiler>'
en7	Supersidd	2024-07-11 14:36:13	0	Tiny change: '^ ^ ^ ^\n\nThe' -> '^ ^ ^\n\nThe'
en6	Supersidd	2024-07-11 14:34:45	37	Tiny change: ' ^ ^\n\n \| \| \| \|\n\nThese ' -> ' ^ ^\n\nThese '
en5	Supersidd	2024-07-11 14:34:01	4
en4	Supersidd	2024-07-11 14:33:43	686
en3	Supersidd	2024-07-11 12:57:50	1027
en2	Supersidd	2024-07-11 12:47:17	331
en1	Supersidd	2024-07-11 12:45:27	2257	Initial revision (saved to drafts)

History