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
- 1 ≤ n ≤ 10^5 (n is odd)
- 0 ≤ a[i] ≤ 10^9
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
- Before the single element, each pair starts at an even index: a[0]=a[1], a[2]=a[3], …
- 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