Single Element in a Sorted Duplicate Array

You are given a sorted array of integers in which every element appears exactly twice, except for exactly one element which appears exactly once. Find and return that single element. Your algorithm must run in O(log n) time and O(1) extra space.

Input: The first line contains the integer n. The second line contains n space-separated integers, the sorted array. Output: Print a single integer: the value that appears exactly once.

1 <= n <= 10^5, n is odd -10^9 <= arr[i] <= 10^9 arr is sorted in non-decreasing order; every value appears exactly twice except exactly one value, which appears exactly once.

This problem's O(log n) time AND O(1) space requirement rules out simpler approaches like XOR-ing everything (which would need O(n) time) or a hash map (O(n) space) - the sorted order specifically is what enables the binary search trick.

In a sorted array where every value appears exactly twice except one, find that one single, unpaired value. Brute force: Scan the array linearly, checking each pair of adjacent elements for a mismatch - this costs O(n), correct but doesn't exploit the sorted structure's exploitable even/odd pairing pattern. Optimised: The observation that pairing parity (even-indexed pair starts) flips exactly at the single element turns this into a genuine binary-search-on-a-monotonic-property problem - checking just ONE pair at a rounded-even mid index per step halves the search range every time, achieving O(log n) instead of a linear scan.

1. Notice that BEFORE the single element, every pair starts at an EVEN index; AFTER it, that parity flips to odd. 2. Round the candidate mid index DOWN to an even index, then compare arr[mid] with arr[mid+1]. 3. If they're equal, the pairing pattern still holds there, so the single element is to the RIGHT; if they differ, the single element is AT OR BEFORE mid.

Time: O(log n) - a binary search exploiting the even/odd pairing parity. Space: O(1) - just a few pointer variables, exactly meeting the problem's O(1) space requirement.

n = 1 (the array has just the single element); the unique element may be the first or the last value in the array.

Be ready to explain the parity argument clearly (why pairs start at even indices before the single element, and odd indices after) - this insight is the entire key to applying binary search here at all.