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).
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. 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.
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 < Keyint 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 <= Keyint 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 > Keyint 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 >= Keyint 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 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. This can be quite problematic 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. Also, I
