33. Search in Rotated Sorted Array

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

Design

The keyword search and the time complexity needs to be in $O(logn)$ mean that the binary search approach should be applied.

Method I

  1. Find the minimum within the array nums, which is the position where rotation occurs.
  2. Apply the binary search approach and mark the position where the read middle value (mid + rot) % nums.length at during each traversal.
Search in Rotated Sorted Array

Method II

https://leetcode.com/problems/search-in-rotated-sorted-array/discuss/14436/Revised-Binary-Search/191339

Implementation

Method I

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

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

    // Find the minimum
    while (left < right) {
      int mid = left + (right - left) / 2;
      if (nums[mid] > nums[right]) { // elements to the right are always greater in a sorted array, so we narrow down the search range once this happens
        left = mid + 1;
      } else {
        right = mid;
      }
    }

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

    // Binary Search
    while (left <= right) {
      int mid = left + (right - left) / 2;
      int realmid = (mid + rot) % nums.length;
      if (nums[realmid] > target) {
        right = mid - 1;
      } else if (nums[realmid] < target) {
        left = mid + 1;
      } else {
        return realmid;
      }
    }

    return -1;
  }
}

Method II

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

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

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

      // If the array is sorted on the left part
      if (nums[mid] >= nums[left]) {
        // Use ">=" to make sure that the target is in the left part, then drop the right part
        if (target >= nums[left] && target < nums[mid]) {
          right = mid - 1;
        } else {
          left = mid + 1;
        }
      } else { // If the array is sorted on the right part
        // Use "<=" to make sure that the target is in the right part, then drop the left part
        if (target <= nums[right] && target > nums[mid]) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }
    }

    return -1;
  }
}

Complexity Analysis

Method I

Time: $O(logn)$

Space: $O(1)$

Method II

Time: $O(n)$ ($O(n/2)$)

Space: $O(1)$