Implement Lower Bound in a Sorted Array

105.8k
0

Given a sorted array of integers arr and a target value x, find the index of the lower bound of x. The lower bound is defined as the index of the first element in the array which is greater than or equal to x. If all elements in the array are smaller than x, return the size of the array N.

Example 1

Input: arr = [1, 3, 5, 7, 9, 11], x = 5

Output: 2

Explanation: The first element that is greater than or equal to 5 is 5 itself, which is located at index 2.

Example 2

Input: arr = [1, 3, 5, 7, 9, 11], x = 6

Output: 3

Explanation: 6 is not in the array. The first element greater than or equal to 6 is 7, which is located at index 3.

Brute Force Approach

The most direct idea is to move from left to right and stop at the first position where the value becomes greater than or equal to X.

This works because the lower bound is defined as the first such index. So once that index is found, there is no need to check anything after it.

If the loop finishes without finding such a value, that means every element is smaller than X, so the answer must be the length of the array.

Algorithm

  • Start from index 0 and check each element one by one.

  • If the current element is greater than or equal to X, return that index immediately because it is the first valid lower bound position.

  • If no such element is found after scanning the whole array, return the length of the array.

Key Points

  • If every element is smaller than X, return N.

  • If X is smaller than or equal to the first element, the answer is 0.

  • If duplicate values equal to X exist, return the first such index.

Dry Run

Lower Bound Brute Dry Run

Lower Bound Brute Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Returns the first index where the array value
is greater than or equal to x.
*/
int lowerBound(vector<int>& arr, int x) {
// Check each position from left to right.
for (int i = 0; i < (int)arr.size(); i++) {
// The first value greater than or equal to x
// is the lower bound.
if (arr[i] >= x) {
return i;
}
}
return (int)arr.size();
}
};
// Driver code starts
int main() {
vector<int> arr = {2, 3, 7, 10, 11, 11, 25};
int x = 11;
Solution obj;
cout << obj.lowerBound(arr, x) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), N is the length of array, because in the worst case the whole array may need to be scanned.

Space Complexity: O(1), because only a loop variable is used.

Optimal Approach

The useful observation is this: when arr[mid] is already greater than or equal to X, that index might be the answer, but there may still be another valid index on the left side.

So that position should be remembered, and the search should continue toward the left half.

If arr[mid] is smaller than X, then the entire left side including mid becomes useless, because none of those values can be the first index with arr[index] >= X.

This is why lower bound is slightly different from normal binary search. The search does not stop at the first valid position. It keeps trying to find an earlier valid one.

Algorithm

  • Start with two pointers, low at 0 and high at the last index, because the answer can lie anywhere in the array.

  • Keep a variable answer as the length of the array. This is useful because if no valid index is found, that default value itself becomes the final answer.

  • Find the middle index using mid = low + (high - low) / 2 so the middle position is calculated safely.

  • If arr[mid] >= X, store mid in answer because it is a valid lower bound candidate, then move left to check whether an even smaller valid value exists.

  • If arr[mid] < X, move right because the lower bound cannot lie at mid or anywhere before it.

  • Continue until low becomes greater than high.

  • Return answer.

Dry Run

Lower Bound Optimal Dry Run

Lower Bound Optimal Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Returns the first index where the array value
is greater than or equal to x.
*/
int lowerBound(vector<int>& arr, int x) {
// Left boundary of the current search range.
int low = 0;
// Right boundary of the current search range.
int high = (int)arr.size() - 1;
// Starts as arr.size() so it remains correct when no lower bound exists.
int answer = (int)arr.size();
// Keep searching while a valid range still exists.
while (low <= high) {
// Calculate the middle index safely.
int mid = low + (high - low) / 2;
// This index is valid, so store it and try to find an earlier one.
if (arr[mid] >= x) {
answer = mid;
high = mid - 1;
} else {
// Values up to mid are too small, so move to the right half.
low = mid + 1;
}
}
return answer;
}
};
// Driver code starts
int main() {
vector<int> arr = {2, 3, 7, 10, 11, 11, 25};
int x = 11;
Solution obj;
cout << obj.lowerBound(arr, x) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(log N), N is the length of the array, because the search range becomes half in each step.

Space Complexity: O(1), because only a few variables are used.

Interview follow-up Questions

That happens when every element in the array is smaller than X, so no valid index satisfies arr[index] >= X.

Two PointerSortingMathsGreedyBinary SearchArrays

Read Similar Blogs

Arrays

Row wise traversal

Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1 2 3 , then second row prints as 4 5 6 . Input: mat = [[10, 20], [30, 40], [50, 60]] Output: 10 20 30 40 50...

61.7k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cells are mat[0][0...

67k
Arrays

Search Element in Matrix

Given a matrix with N rows and M columns and a target value X , search for X in the matrix. Return the position of the first occurrence of X as {row, col} . Return {-1, -1} when the target value is...

98.4k
Comments0