540. Single Element in a Sorted Array

T: O(logn)

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            if (left == right) { // when equal -> find the only one number
                return nums[left];
            }
            int mid = left + (right - left)/2;
            if (nums[mid] != nums[mid-1] && nums[mid] != nums[mid+1]) { // not equal to neighbor -> find the only one number
                return nums[mid];
            } else if (nums[mid] == nums[mid-1]) { // ex: [1,1,2,3,3,4,4,8,8]
                int leftPart = mid - 1 - left;
                if (leftPart % 2 == 1) {
                    right = mid - 2;
                } else {
                    left = mid + 1;
                }
            } else if (nums[mid] == nums[mid+1]) {
                int rightPart = right - (mid + 1);
                if (rightPart % 2 == 1) {
                    left = mid + 2;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
     }
}

/**
T: O(logn)

ex: else if (nums[mid] == nums[mid-1])
 0 1 2 3
[1,1,2,3,3,4,4,8,8]
         m
     r
 l     

ex: else if (nums[mid] == nums[mid+1])
0 1 2 3 4
1 1 3 3 4
    m 
 */