Finding the Single Non-Duplicate Element in a Sorted Array: A Binary Search

Situation:

You are given a sorted array of integers where every element appears exactly twice, except for one element that appears only once. Find and return the single element that does not have a duplicate.

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

Explanation: The number 2 appears only once, while all other numbers appear twice.

Example 2:

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

Explanation: The number 10 appears only once, while all other numbers appear twice.

Constraints:

1. The array is sorted in non-decreasing order.
2. The array will always have exactly one element that appears once, and all other elements appear twice.
3. The solution must run in O(log N) time and use O(1) space.

Action:

1. To solve the array question in logN time we need some binary search
2. We need a variation of binary search

How can we tweak our binary search?

Why Compare Based on Even/Odd Index?

Mid At Even

            l           m           r
            0. 1  2. 3. 4. 5. 6. 7. 8 
           [1, 1, 2, 3 ,3, 4, 4, 8, 8]      

Mid @ Odd

           l.       m        r 
           0. 1  2. 3. 4. 5. 6
          [3, 3, 5, 5, 6, 7, 7 ] 

In a sorted array where every element appears exactly twice except for one, the pairs of duplicates will follow a specific pattern:

1. Before the single element: Pairs start at even indices.
2. After the single element: Pairs start at odd indices.

This pattern allows us to determine whether the single element is on the left or right side of the middle index.

If mid is even:

Compare nums[mid] with nums[mid + 1]

• If they are the same, the single element must be on the right side (because pairs are intact on the left).
• If they are different, the single element must be on the left side (because the pair is broken).

Our Strategy:

1. Pairs start at the even index
2. Landing on even index, pair of it must be on the right side i.e next index is odd
3. if we found it, single element must be on the right side
4. else left side
5. Landing on odd index, we assume, the pair of it must be on the left side, i.e prev index which is odd.
6. if we found it, the single element is on the right side
7. else left side

function binarySearch(){
        
let l = 0, r = nums.length - 1

while (l < r) {
    let mid = Math.floor((l + r) / 2)

    if (mid % 2 === 0) {
        
    // at even index pair start
    if (nums[mid] === nums[mid + 1]) {
            // go right
            l = mid + 2
        } else {
            // go left
            r = mid
        }
    } else {

  // at odd index, the pair lies in prev index i.e even
   if (nums[mid] === nums[mid - 1]) {
            // we found a pair 
            // go right
            l = mid + 1

        } else {
            //go left
            r = mid
        }
    }
}
return nums[l]
}

This can be simplified here: by adjusting mid to always fall on the mid @ even index

• By ensuring mid is even,
• we simplify the logic and always compare nums[mid] with nums[mid + 1].
• The binary search halves the search space in each iteration, making it efficient.

function binarySearch(){
  let l = 0, r = nums.length - 1
  while(l < r){
    let mid = Math.floor((l + r) / 2)

    if(mid % 2 === 1){
          mid--
         // mid is always even
     }
    if(nums[mid] === nums[mid + 1]){
       //go right
        l = mid + 2
     }else{
      // go left
      r = mid  
     }
   }
  return nums[l]
};

l = mid + 2

r = mid

1. Jumping by 2 ensures we skip intact pairs and efficiently narrow down the search space.
2. Staying at mid ensures we don't miss the single element when the pair is broken.