The problem quoted:
https://leetcode.com/problems/single-element-in-a-sorted-array/
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.
The answer:
var singleNonDuplicate = function(nums) {
var low = 0, high = nums.length - 2, mid;
while (low < high) {
mid = low + Math.floor((high - low) / 2);
if (mid % 2 === 1) mid--; // make sure it is even
if (nums[mid] !== nums[mid+1]) { // the single element already happened on the left
high = mid - 1;
} else {
low = mid + 2;
}
}
return nums[low];
};
The fourth line:
while (low < high) {
if changed to
while (low <= high) {
can also pass all tests on the website. But which version is correct or more robust?
I also had to decide whether it is better to set the initial high to
high = nums.length - 2
or to
high = nums.length - 1
The same with
high = mid - 1;
I wonder if it is best to set it to mid - 1 or mid - 2.
It seems it can be complicated near the "end game", when there are 3, 5, 7, 9 remaining array elements, when the mid, low, high can be calculated in the way that the loop will not terminate or find the incorrect answer. If there are many elements remaining, such as 21, 31, etc, the algorithm in general works. It seems you have to consider the small cases when the number of remaining elements is small.
