81. Search in Rotated Sorted Array II

Source link: https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

Design

https://leetcode.com/problems/search-in-rotated-sorted-array-ii/discuss/28202/Neat-JAVA-solution-using-binary-search

Implementation

class Solution {
  public boolean search(int[] nums, int target) {
    if (nums.length == 0 || nums == null) return false;

    int left = 0, right = nums.length - 1;

    while (left <= right) {
      int mid = left + (right - left) / 2;
      if (nums[mid] == target) return true;

      // If left part is sorted
      if (nums[mid] > nums[left]) {
        if (target < nums[left] || target > nums[mid]) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
        // If right part is rotated
      } else if (nums[mid] < nums[left]) {
        if (target < nums[mid] || target > nums[right]) {
          right = mid - 1;
        } else {
          left = mid + 1;
        }
      } else {
        // If we get here, that means nums[left] == nums[mid] == nums[right], then shifting out
        // any of the two sides won't change the result but can help remove duplicates from
        // consideration, here we just use left++ but right-- works too
        left++;
      }
    }

    return false;
  }
}

Complexity Analysis

Time: $O(n)$

Space: $O(1)$