Getting everything ready for you…

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

0s

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

Example 1

Input

4
1 2 2 3
2

Output

1

Example 2

Input

5
3 5 8 15 19
9

Output

3

Hints

  1. The condition a[i] ≥ x is false for a prefix of the array and true for the rest.
  2. 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);
    }
}

Solve Lower Bound online · All practice problems