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
- 1 ≤ n ≤ 10^5
- -10^9 ≤ a[i], target ≤ 10^9
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
- You want the first index whose value is ≥ target.
- 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);
}
}