Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. First occurrence = the first index with a[i] ≥ x (if that element equals x).
  2. 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