⬅ Previous Topic
Find Rotation Count in Sorted ArrayNext Topic ⮕
Find Peak Element in Array⬅ Previous Topic
Find Rotation Count in Sorted ArrayNext Topic ⮕
Find Peak Element in ArrayTopic Contents
You are given a sorted array where every element appears exactly twice, except one element that appears only once. Your task is to find and return the single non-repeating element.
Note: The array is sorted in non-decreasing order. There will always be exactly one such unique element in the array.
If the array is empty, return null
or an appropriate message indicating that the array is invalid.
start = 0
and end = n - 2
.start ≤ end
:mid = start + (end - start) / 2
.mid
is even:arr[mid] == arr[mid + 1]
, the unique element is on the right → start = mid + 2
.end = mid
.mid
is odd:arr[mid] == arr[mid - 1]
, the unique element is on the right → start = mid + 1
.end = mid - 1
.start
index points to the single element.public class SingleElementFinder {
public static int singleNonDuplicate(int[] arr) {
int start = 0, end = arr.length - 2;
while (start <= end) {
int mid = start + (end - start) / 2;
// Pair index logic: even-indexed element should match with next, odd with previous
if ((mid % 2 == 0 && arr[mid] == arr[mid + 1]) ||
(mid % 2 == 1 && arr[mid] == arr[mid - 1])) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return arr[start];
}
public static void main(String[] args) {
int[] arr = {1, 1, 2, 2, 3, 4, 4};
System.out.println("Single Element: " + singleNonDuplicate(arr));
}
}
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(1) | If the unique element is found at the first mid index. |
Average Case | O(log n) | Binary search reduces the search space by half in every step. |
Worst Case | O(log n) | Even in the worst case, binary search checks only log(n) elements. |
O(1)
Explanation: Only a few variables (start, end, mid) are used regardless of input size.
⬅ Previous Topic
Find Rotation Count in Sorted ArrayNext Topic ⮕
Find Peak Element in ArrayYou can support this website with a contribution of your choice.
When making a contribution, mention your name, and programguru.org in the message. Your name shall be displayed in the sponsors list.