33. Search in Rotated Sorted Array - cocoder39/coco39_LC GitHub Wiki

33. Search in Rotated Sorted Array

update: below thinking process is more intuitive

  • step 1: identify if mid falls in left segment or right segment
    • nums[mid] >= nums[0]: left segment
    • nums[mid] <= nums[-1]: right segment
  • step 2: based on decision at step 1, we identify sorted range
    • if mid is in left segment, sorted range is [0, mid]
    • if mis is in right segment, sorted range is [mid, -1]
  • step 3: identify if target is within the sorted range, reduce search space accordingly

additionally, this solution works for array that is not rotated where nums[mid] >= nums[0] is always true

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums)-1
        while low + 1 < high:
            mid = low + (high - low) // 2
            if nums[mid] == target:
                return mid
            # mid falls in left asecnding segment
            elif nums[mid] >= nums[0]: 
                # [0, mid] is sorted
                if nums[0] <= target < nums[mid]:
                    high = mid
                else:
                    low = mid
            # mid falls in right asecnding segment
            else: # nums[mid] <= nums[-1] 
                # [mid, -1] is sorted 
                if nums[mid] < target <= nums[-1]:
                    low = mid
                else:
                    high = mid
        
        if nums[low] == target:
            return low
        if nums[high] == target:
            return high
        return -1

===================================

  • step 1: find the sorted subarray within the rotated sorted array, it is either between [low, mid+1] or [mid, right+1]
    • compare nums[mid] with either nums[left] or nums[right]
      • if nums[left] <= nums[mid], then [left, mid+1] is ascending sorted
      • if nums[mid] <= nums[right], then [mid, right+1] is ascending sorted
      • either one of above strategy can be selected. The 2 solutions below are based on each of them
  • step 2: check if target falls into the sorted subarray found at step 1.
    • If yes, narrowing down the search space to the sorted subarray
    • if no, discard the sorted subarray and continue binary search
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)-1
        while left + 1 < right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid

            # subarray on mid's right is sorted
            if nums[mid] <= nums[right]:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
            else: # subarray on mid's left is sorted
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
        
        if nums[left] == target:
            return left
        if nums[right] == target:
            return right
        return -1

or

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)-1
        while left + 1 < right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid

            # subarray on mid's left is sorted
            if nums[mid] >= nums[left]:
                if nums[left] <= target < nums[mid]:
                    right = mid-1
                else:
                    left = mid + 1
            else: # subarray on mid's right is sorted
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        
        if nums[left] == target:
            return left
        if nums[right] == target:
            return right
        return -1

=============================================

(1) mid is at left 1.1 target is at left 1.2 target is at right

(2) mid is at right 2.1 target is at left 2.2 target is at right

int search(vector<int>& nums, int target) {
        int start = 0, end = nums.size() - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] >= target) {
                if (nums[mid] >= nums[0] && target < nums[0]) { //mid is at left, target is at right
                    start = mid;
                } else { // mid and target are at same side
                    end = mid;
                }
            } else { // (nums[mid] < target)
                if(nums[mid] < nums[0] && target >= nums[0]) { //mid is at right and target at left
                    end = mid;
                } else { // mid and target are at same side
                    start = mid;
                }
            }
        }
        
        if (nums[start] == target) {
            return start;
        } else if (nums[end] == target) {
            return end;
        } else {
            return -1;
        }
    }
⚠️ **GitHub.com Fallback** ⚠️