Problem Statement: Given a sorted array of N integers and an integer x, write a program to find the lower bound of x.
Pre-requisite: Binary Search algorithm
Examples
Example 1:
Input Format: N = 4, arr[] = {1,2,2,3}, x = 2
Result: 1
Explanation: Index 1 is the smallest index such that arr[1] >= x.
Example 2:
Input Format: N = 5, arr[] = {3,5,8,15,19}, x = 9
Result: 3
Explanation: Index 3 is the smallest index such that arr[3] >= x.
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution:
In the preceding article, we comprehensively explored the implementation of the Binary Search algorithm.
The primary objective of the Binary Search algorithm is to efficiently determine the appropriate half to eliminate, thereby reducing the search space by half. It does this by determining a specific condition that ensures that the target is not present in that half.
In this article, we will learn how to implement the lower bound algorithm using a slight modification of the Binary Search algorithm.
Let’s start.
What is Lower Bound?
The lower bound algorithm finds the first or the smallest index in a sorted array where the value at that index is greater than or equal to a given key i.e. x.
The lower bound is the smallest index, ind, where arr[ind] >= x. But if any such index is not found, the lower bound algorithm returns n i.e. size of the given array.
Brute Force Approach
Algorithm / Intuition
Naive approach (Using linear search):
Let’s understand how we can find the answer using the linear search algorithm. With the knowledge that the array is sorted, our approach involves traversing the array starting from the beginning. During this traversal, each element will be compared with the target value, x. The index, i, where the condition arr[i] >= x is first satisfied, will be the answer.
Code
#include <bits/stdc++.h>
using namespace std;
int lowerBound(vector<int> arr, int n, int x) {
for (int i = 0; i < n; i++) {
if (arr[i] >= x) {
// lower bound found:
return i;
}
}
return n;
}
int main()
{
vector<int> arr = {3, 5, 8, 15, 19};
int n = 5, x = 9;
int ind = lowerBound(arr, n, x);
cout << "The lower bound is the index: " << ind << "\n";
return 0;
}
Output: The lower bound is the index: 3
import java.util.*;
public class tUf {
public static int lowerBound(int []arr, int n, int x) {
for (int i = 0; i < n; i++) {
if (arr[i] >= x) {
// lower bound found:
return i;
}
}
return n;
}
public static void main(String[] args) {
int[] arr = {3, 5, 8, 15, 19};
int n = 5, x = 9;
int ind = lowerBound(arr, n, x);
System.out.println("The lower bound is the index: " + ind);
}
}
Output: The lower bound is the index: 3
def lowerBound(arr: [int], n: int, x: int) -> int:
for i in range(n):
if arr[i] >= x:
#lower bound found
return i
return n
if __name__ == "__main__":
arr = [3, 5, 8, 15, 19]
n = 5
x = 9
ind = lowerBound(arr, n, x)
print("The lower bound is the index:", ind)
Output: The lower bound is the index: 3
function lowerBound(arr, n, x) {
for (let i = 0; i < n; i++) {
if (arr[i] >= x) {
// lower bound found:
return i;
}
}
return n;
}
let arr = [3, 5, 8, 15, 19];
let n = 5, x = 9;
let ind = lowerBound(arr, n, x);
console.log("The lower bound is the index:", ind);
Output: The lower bound is the index: 3
Complexity Analysis
Time Complexity: O(N), where N = size of the given array.
Reason: In the worst case, we have to travel the whole array. This is basically the time complexity of the linear search algorithm.
Space Complexity: O(1) as we are using no extra space.
Optimal Approach
Algorithm / Intuition
Optimal Approach (Using Binary Search):
As the array is sorted, we will apply the Binary Search algorithm to find the index. The steps are as follows:
We will declare the 2 pointers and an ‘ans’ variable initialized to n i.e. the size of the array(as If we don’t find any index, we will return n).
- Place the 2 pointers i.e. low and high: Initially, we will place the pointers like this: low will point to the first index, and high will point to the last index.
- Calculate the ‘mid’: Now, we will calculate the value of mid using the following formula:
mid = (low+high) // 2 ( ‘//’ refers to integer division) - Compare arr[mid] with x: With comparing arr[mid] to x, we can observe 2 different cases:
- Case 1 – If arr[mid] >= x: This condition means that the index mid may be an answer. So, we will update the ‘ans’ variable with mid and search in the left half if there is any smaller index that satisfies the same condition. Here, we are eliminating the right half.
- Case 2 – If arr[mid] < x: In this case, mid cannot be our answer and we need to find some bigger element. So, we will eliminate the left half and search in the right half for the answer.
The above process will continue until the pointer low crosses high.
Dry run: Please refer video for it.
Code
#include <bits/stdc++.h>
using namespace std;
int lowerBound(vector<int> arr, int n, int x) {
int low = 0, high = n - 1;
int ans = n;
while (low <= high) {
int mid = (low + high) / 2;
// maybe an answer
if (arr[mid] >= x) {
ans = mid;
//look for smaller index on the left
high = mid - 1;
}
else {
low = mid + 1; // look on the right
}
}
return ans;
}
int main()
{
vector<int> arr = {3, 5, 8, 15, 19};
int n = 5, x = 9;
int ind = lowerBound(arr, n, x);
cout << "The lower bound is the index: " << ind << "\n";
return 0;
}
Output: The lower bound is the index: 3
import java.util.*;
public class tUf {
public static int lowerBound(int []arr, int n, int x) {
int low = 0, high = n - 1;
int ans = n;
while (low <= high) {
int mid = (low + high) / 2;
// maybe an answer
if (arr[mid] >= x) {
ans = mid;
//look for smaller index on the left
high = mid - 1;
} else {
low = mid + 1; // look on the right
}
}
return ans;
}
public static void main(String[] args) {
int[] arr = {3, 5, 8, 15, 19};
int n = 5, x = 9;
int ind = lowerBound(arr, n, x);
System.out.println("The lower bound is the index: " + ind);
}
}
Output: The lower bound is the index: 3
def lowerBound(arr: [int], n: int, x: int) -> int:
low = 0
high = n - 1
ans = n
while low <= high:
mid = (low + high) // 2
# maybe an answer
if arr[mid] >= x:
ans = mid
# look for smaller index on the left
high = mid - 1
else:
low = mid + 1 # look on the right
return ans
if __name__ == "__main__":
arr = [3, 5, 8, 15, 19]
n = 5
x = 9
ind = lowerBound(arr, n, x)
print("The lower bound is the index:", ind)
Output: The lower bound is the index: 3
function lowerBound(arr, n, x) {
let low = 0, high = n - 1;
let ans = n;
while (low <= high) {
let mid = Math.floor((low + high) / 2);
// maybe an answer
if (arr[mid] >= x) {
ans = mid;
// look for smaller index on the left
high = mid - 1;
}
else {
low = mid + 1; // look on the right
}
}
return ans;
}
let arr = [3, 5, 8, 15, 19];
let n = 5, x = 9;
let ind = lowerBound(arr, n, x);
console.log("The lower bound is the index:", ind);
Output: The lower bound is the index: 3
Complexity Analysis
Time Complexity: O(logN), where N = size of the given array.
Reason: We are basically using the Binary Search algorithm.
Space Complexity: O(1) as we are using no extra space.
Video Explanation
Special thanks to KRITIDIPTA GHOSH for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article