Getting everything ready for you…

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

0s

Practice › Binary Search

Single Element in a Sorted Array

Medium · Binary Search · Asked at Amazon, Google, Microsoft, Nvidia

In the sorted array, every value appears exactly twice except one value that appears once. Print that value in O(log n).

Input

First line: n. Second line: n space-separated integers.

Output

The single value.

Constraints

Before the single element, pairs start at even indices; after it, at odd indices. Binary search on that property.

Example 1

Input

9
1 1 2 3 3 4 4 8 8

Output

2

Example 2

Input

7
3 3 7 7 10 11 11

Output

10

Hints

  1. Before the single element, each pair starts at an even index: a[0]=a[1], a[2]=a[3], …
  2. After it, pairs start at odd indices. Check the pair around mid (make mid even) to decide which side the single element is on.

Approach

Binary search over even indices. Let mid be even (decrement it if odd). If a[mid] == a[mid + 1], the pairs are still aligned up to mid, so the single element is to the right: lo = mid + 2. Otherwise the alignment broke at or before mid: hi = mid. When lo == hi, a[lo] is the answer.

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 &x : a) cin >> x;
    int lo = 0, hi = n - 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (mid % 2 == 1) mid--;
        if (a[mid] == a[mid + 1]) lo = mid + 2;
        else hi = mid;
    }
    cout << a[lo] << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
a = data[1:]
lo, hi = 0, len(a) - 1
while lo < hi:
    mid = (lo + hi) // 2
    if mid % 2 == 1:
        mid -= 1
    if a[mid] == a[mid + 1]:
        lo = mid + 2
    else:
        hi = mid
print(a[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[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextLong();
        int lo = 0, hi = n - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (mid % 2 == 1) mid--;
            if (a[mid] == a[mid + 1]) lo = mid + 2;
            else hi = mid;
        }
        System.out.println(a[lo]);
    }
}

Solve Single Element in a Sorted Array online · All practice problems