Find the Element that Appears Once in a Sorted Array in O(logn)

Given a sorted array of integers. In this array, every element appears twice except one element which appears only once. Write a code to find the element which appears only once.

In this tutorial, I have explained how we can find the element that appears once in a sorted array in O(logn) time complexity and by using constant space.

Example 1:

Input: [1, 1, 2, 2, 3, 4, 4, 7, 7]
Output: 3 (3 appears once in an array)

Example 2:

Input: [1, 1, 2, 2, 3, 3, 4, 5, 5]
Output: 4

Note: Try to solve this problem in O(logn) time complexity and by using constant space O(1).

[prajwal]

Actually I was lookinng for a O(logn) solution. This video explains it well. Thanks.

[abhinav]

A very nice video. Just a simple suggestion. Since you spend a lot of time in finding problems, coming up with multiple solutions, writing code for each solution with brilliant comments.
I would suggest you to write a script for narrating through the video. I personally feel this is a channel with huge potential. Best of luck and thanks a lot for your hard work bro...

[shikhajain]

Thanks. With The very first approach the array like 122334455, it is failing!!
Also with BinarySearch approach can be find multiple single element?

[ninalounici]

hello, I don't understand why is the space complexity O(1)?

[awneeshsingh]

what will be the approach to find the element occurring once if other numbers can occur any number of times?

[ashishdas]

Better if one goes with binary search since the array is already sorted

[ruchisaxena]

for your first approach what will be the output if array is like this 1122233455

[freeadvice-tamil]

class Hello {
public static void main(String[] args) {
int[] arr = {1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 6};
int result = findTheElement(arr);
System.out.println(result);
}

private static int findTheElement(int[] arr) {
int start = 0;
int end = arr.length - 1;

while (start <= end) {
int mid = start + (end - start) / 2;

if (start == end) {
return arr[start]; // Single element found
}

if (mid % 2 == 0) { //if even
if (arr[mid] == arr[mid + 1]) {
start = mid + 2;
} else {
end = mid;
}
} else {
if (arr[mid] == arr[mid - 1]) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
return -1;
}
}