Practice › Binary Search
Lower Bound
Easy · Binary Search · Asked at TCS, Infosys, Wipro, Amazon
Print the first index i (0-based) with a[i] ≥ x. If no such index exists, print n.
Input
First line: n. Second line: n sorted integers. Third line: x.
Output
The lower-bound index.
Constraints
- 1 ≤ n ≤ 10^5
- The array is sorted in non-decreasing order
Example 1
Input
4 1 2 2 3 2
Output
1
Example 2
Input
5 3 5 8 15 19 9
Output
3
Hints
- The condition a[i] ≥ x is false for a prefix of the array and true for the rest.
- Binary search for the first index where it becomes true; use hi = n so "not found" naturally returns n.
Approach
Search the half-open range [lo, hi) = [0, n). If a[mid] >= x, the answer is mid or to its left (hi = mid). Otherwise it's to the right (lo = mid + 1). When lo meets hi, that's the first index with a[i] ≥ x, or n if there's none. This is exactly std::lower_bound / Python's bisect_left.
Complexity: O(log n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n);
for (auto &v : a) cin >> v;
long long x;
cin >> x;
int lo = 0, hi = n;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] >= x) hi = mid;
else lo = mid + 1;
}
cout << lo << "\n";
return 0;
}Python solution
import sys
from bisect import bisect_left
data = list(map(int, sys.stdin.read().split()))
n = data[0]
a, x = data[1 : n + 1], data[n + 1]
print(bisect_left(a, x))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
long x = sc.nextLong();
int lo = 0, hi = n;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] >= x) hi = mid;
else lo = mid + 1;
}
System.out.println(lo);
}
}