81. Search in Rotated Sorted Array II

• 81. Search in Rotated Sorted Array II
  • Description
  • Intuition
  • Pitfall
  • Solution

Description

Here\

Intuition

Very alike with 033

Pitfall

There is no O(log N) solution when duplicated elements exist

Solution

If we found the nums[left] == nums[mid] && nums[mid] == nums[right], we can move the left and right to the center until the condition is false. For example, 5 5 5 5 5 5 1 5 5

At that time, the side who breaks the condition will be sorted; in the above case, it will be right side. then we can find decide which side to go.

public boolean search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
      final int mid = left + (right - left) / 2;
      if (nums[mid] == target) {
        return true;
      } else if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
        --right;
        ++left;
      } else if (nums[mid] <= nums[right]) { // right side is sorted
        if (nums[mid] <= target && target <= nums[right]) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      } else {
        assert (nums[left] <= nums[mid]);
        if (nums[left] <= target && target <= nums[mid]) {
          right = mid - 1;
        } else {
          left = mid + 1;
        }
      }
    }
    return false;
}