81. Search in Rotated Sorted Array II

#binary-search

Problem

Search in Rotated Sorted Array II - LeetCodeLeetCode

Intuition

The intuition is same as 33. Search in Rotated Sorted Array, but the optimisation we could do is based on what all values we have access to. If they are same, then we move low to right and high to left.

// From the position I am in i cant see all the values, but I will have
// access to values in indices low, mid and high. 
// If they all are equal, then move low to left and high to right.
if(nums[low] == nums[mid] && nums[mid] == nums[high]) {
    low = low + 1;
    high = high - 1;
    continue;
}

Time Complexity

O(log n)

Space Complexity

O(n)

Solution

class Solution {
    public boolean search(int[] nums, int target) {
        int low = 0, high = nums.length - 1;


        while(low <= high) {
            int mid = low + (high-low)/2;

            if(nums[mid] == target) {
                return true;
            }
            // From the position I am in i cant see all the values, but I will have
            // access to values in indices low, mid and high. 
            // If they all are equal, then move low to left and high to right.
            if(nums[low] == nums[mid] && nums[mid] == nums[high]) {
                low = low + 1;
                high = high - 1;
                continue;
            }

            if(nums[low] <= nums[mid]) { // Left sorted
                if(nums[low] <= target && target < nums[mid]) { // Search left
                    high = mid-1;
                } else { // Else search right
                    low = mid + 1;
                }
            } else { // Right sorted 
                if(nums[mid] < target && target <= nums[high]) { // Search right
                    low = mid + 1;
                } else { // Else search left
                    high = mid - 1;
                }
            }
        }
        
        return false;
    }
}