#LeetCode:Single Element in a Sorted Array

Also Check: Solutions Of May LeetCoding Challenge (2020)

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once.

Example 1:
Input: [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2:
Input: [3,3,7,7,10,11,11]
Output: 10

Note: Your solution should run in O(log n) time and O(1) space.

Algorithm:
1). "Every element appears exactly twice, except for one element which appears exactly once." This means length of the array would be always odd.
2). If the length is one, return the first element.
3). We will start iterating the array, by declaring 2 points i & j. Element at ith and jth position will be consecutive.
4). If element at ith position is not equal to element at jth position, return the ith element, else increment the j with 2.
5). If no such element is encountered, we can confidently return the last element in the sorted array (as it will be the one with out a duplicate value).

GIT URL: Leet Code's Single Element in a Sorted Array problem

Java Solution

ALSO CHECK: Other LeetCode Solutions in Java

-K Himaanshu Shuklaa.