Single Element in a Sorted Array - LeetCode

For any Algorithm question, whenever you see a keyword Sorted think of Binary Search

In the given problem, there is one unique element and rest of all the elements are paired, also the elements are in sorted array

Let’s consider this example, with start and end index pointing to first and last element of the array

nums = [1,1,2,3,3,4,4,8,8]

Now the mid is 3

if you analyze the diagram

• nums[mid] == nums[mid - 1]

Now there are two cases

1. Either the element lies from start to mid
2. Or the element lies from mid to end

You can say the element lies in a part where the length is not even

So the conditions will be

1. if mid to end is even then the element lies from start to mid, so end = mid - 2 . Why mid - 2 because we don’t want to iterate nums[mid] and nums[mid - 1] again
2. if mid to end is odd then the element lies from mid to end, so start = mid + 1

Now Let’s consider a case where nums[mid] == nums[mid + 1]

The conditions for this scenario is

1. if start to mid is even, then element lies from mid to end, so start = mid + 2

2. else end = mid - 1

Now there comes a scenario where nums[mid] is not equal to nums[mid + 1] or nums[mid -1], that’s the element we have to return

Here is the code

var singleNonDuplicate = function(nums) {
	let start = 0, end = nums.length - 1
	while(start <= end) {
		let mid = Math.floor((start + end) / 2)
		if(nums[mid] == nums[mid - 1]) {
			let isEven = (end - mid) % 2 == 0
			if(isEven) {
				end = mid - 2
			} else {
				start = mid + 1
			}
		} else if(nums[mid] == nums[mid + 1]) {
			let isEven = (mid -start) % 2 == 0
			if(isEven) {
				start = mid + 2
			} else {
				end = mid - 1
			}
		} else {
			return nums[mid]
		}
	}
};

This post is also available on DEV.