Practice › Binary Search
First and Last Occurrence
Easy · Binary Search · Asked at Amazon, Microsoft, Google, Flipkart
Print the first and last index (0-based) of x in the sorted array, or -1 -1 if x is not present.
Input
First line: n. Second line: n sorted integers. Third line: x.
Output
first last.
Constraints
- 1 ≤ n ≤ 10^5
Two binary searches: one biased left, one biased right — O(log n).
Example 1
Input
6 5 7 7 8 8 10 8
Output
3 4
Example 2
Input
6 5 7 7 8 8 10 6
Output
-1 -1
Hints
- First occurrence = the first index with a[i] ≥ x (if that element equals x).
- Last occurrence = (first index with a[i] > x) − 1. Two binary searches.
Approach
Run two boundary searches: lower = first i with a[i] >= x and upper = first i with a[i] > x. If lower is n or a[lower] != x, x is absent and the answer is -1 -1. Otherwise the answer is lower and upper − 1. Both searches are O(log n). A linear scan would be O(n).
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 first = lower_bound(a.begin(), a.end(), x) - a.begin();
int last = upper_bound(a.begin(), a.end(), x) - a.begin() - 1;
if (first == n || a[first] != x) cout << "-1 -1\n";
else cout << first << " " << last << "\n";
return 0;
}Python solution
import sys
from bisect import bisect_left, bisect_right
data = list(map(int, sys.stdin.read().split()))
n = data[0]
a, x = data[1 : n + 1], data[n + 1]
first = bisect_left(a, x)
if first == n or a[first] != x:
print(-1, -1)
else:
print(first, bisect_right(a, x) - 1)Java solution
import java.util.*;
public class Main {
// first index with a[i] > x (strict) or a[i] >= x
static int bound(long[] a, long x, boolean strict) {
int lo = 0, hi = a.length;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (strict ? a[mid] > x : a[mid] >= x) hi = mid;
else lo = mid + 1;
}
return lo;
}
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 first = bound(a, x, false);
if (first == n || a[first] != x) System.out.println("-1 -1");
else System.out.println(first + " " + (bound(a, x, true) - 1));
}
}Solve First and Last Occurrence online · All practice problems