Getting everything ready for you…

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

0s

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

Output

The index of x, or -1.

Constraints

Example 1

Input

5
1 3 5 7 9
7

Output

3

Example 2

Input

3
2 4 6
5

Output

-1

Hints

  1. Compare x with the middle element: that tells you which half x must be in.
  2. 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);
    }
}

Solve Binary Search online · All practice problems