#540
Medium Algorithms Single element in a sorted array
Array Binary Search
59.2% acceptance
Feb 19, 2026
12900
243
You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.
Return the single element that appears only once.
Your solution must run in O(log n) time and O(1) space.
Solution
Rust
Time O(n log n)
Space O(1)
impl Solution {
pub fn single_non_duplicate(nums: Vec<i32>) -> i32 {
let mut lo = 0usize;
let mut hi = nums.len() - 1;
while lo < hi {
let mid = ((lo + hi) / 2) & !1;
if nums[mid] == nums[mid + 1] { lo = mid + 2; } else { hi = mid; }
}
nums[lo]
}
}