Getting everything ready for you…

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

0s

Practice › Binary Search

Search Insert Position

Easy · Binary Search · Asked at Amazon, Google, Microsoft, TCS, Infosys

The array is sorted and has distinct values. Print the index (0-based) of target if it is present; otherwise print the index where it would be inserted to keep the array sorted.

Input

First line: n target. Second line: the sorted array.

Output

The index.

Constraints

This is exactly the lower bound: the first index with a[i] ≥ target.

Example 1

Input

4 5
1 3 5 6

Output

2

Example 2

Input

4 2
1 3 5 6

Output

1

Hints

  1. You want the first index whose value is ≥ target.
  2. Binary search with lo = 0, hi = n (n itself is a valid answer when target is larger than everything).

Approach

Lower bound: keep the invariant that the answer lies in [lo, hi]. If a[mid] < target, the answer is after mid (lo = mid + 1); otherwise mid could be the answer (hi = mid). When lo == hi, that is the insert position — and if the target is present, it is its index.

Complexity: O(log n) time · O(1) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    long long t;
    cin >> n >> t;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (a[mid] < t) lo = mid + 1;
        else hi = mid;
    }
    cout << lo << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n, t, a = data[0], data[1], data[2:]
lo, hi = 0, n
while lo < hi:
    mid = (lo + hi) // 2
    if a[mid] < t:
        lo = mid + 1
    else:
        hi = mid
print(lo)

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 t = sc.nextLong();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextLong();
        int lo = 0, hi = n;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (a[mid] < t) lo = mid + 1;
            else hi = mid;
        }
        System.out.println(lo);
    }
}

Solve Search Insert Position online · All practice problems