Practice › Binary Search
Binary Search
Medium · Binary Search · Asked at Amazon, Microsoft, TCS, Infosys, Wipro
Given a sorted array of n distinct integers and a value x, print the index of x (0-based), or -1 if it is not present.
Input
- First line:
n - Second line:
nsorted integers - Third line:
x
Output
The index of x, or -1.
Constraints
- 1 ≤ n ≤ 10^5 — aim for O(log n).
Example 1
Input
5 1 3 5 7 9 7
Output
3
Example 2
Input
3 2 4 6 5
Output
-1
Hints
- Compare x with the middle element: that tells you which half x must be in.
- Keep lo ≤ hi, and compute mid as lo + (hi − lo) / 2 to avoid overflow.
Approach
Keep the search range [lo, hi]. Look at a[mid]: if it equals x, you're done. If it's smaller, x can only be to the right (lo = mid + 1), otherwise to the left (hi = mid − 1). Each step halves the range, so 10^5 elements take about 17 comparisons. If the range becomes empty, print -1.
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 - 1, ans = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == x) { ans = mid; break; }
if (a[mid] < x) lo = mid + 1;
else hi = mid - 1;
}
cout << ans << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n = data[0]
a, x = data[1 : n + 1], data[n + 1]
lo, hi, ans = 0, n - 1, -1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == x:
ans = mid
break
if a[mid] < x:
lo = mid + 1
else:
hi = mid - 1
print(ans)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 - 1, ans = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == x) { ans = mid; break; }
if (a[mid] < x) lo = mid + 1;
else hi = mid - 1;
}
System.out.println(ans);
}
}