CODEWITHSUNDEEP
algorithmbinary-search
Mike Chan
Mike Chan

Reputation: 347

Search in Rotated Array

LC Question: https://leetcode.com/problems/search-in-rotated-sorted-array/

 var search = function(nums, target) {

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

    while (left < right) {

        let mid = left + Math.floor((right - left) / 2); 

        else if (nums[mid] < nums[right]) { //Right side of array is sorted
            if (target > nums[mid] && target <= nums[right]) left = mid + 1; //Target is on right side
            else right = mid
        } else{
            if (target > nums[mid] || target < nums[left]) left = mid + 1; //???
            else right = mid;
        } 
    }
    return nums[left]==target;
};

Could someone explain why if the right side is not sorted, and if target < nums[left] we recalibrate our search space to look right? What kind of situations would lead to this condition being true?

Upvotes: 1

Views: 222

Answers (1)

Daniel Hao
Daniel Hao

Reputation: 4980

@MikeChan, instead of answering your question, it's prob. easier to read the code with embedded notes/explanations:

 def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        
        while left <= right:
            mid = (left + right) // 2
            # if found target value, return the index
            if nums[mid] == target:
                return mid
            
            # determine it's left rotated or right rotated
            """
            No rotated:
            1 2 3 4 5 6 7 8 9 10
                         mid
                 
            left rotated: pivot at the left side of the origin sorted array, A[mid] >= A[left]
            6 7 8 9 10 1 2 3 4 5
               mid
            search in A[left] ~ A [mid] if A[left] <= target < A[mid] else, search right side
            
            right rotated: pivot at the right side of the origin sorted array, A[mid] < A[left]
            6 7 8 9 10 1 2 3 4 5 
               mid          
            search in A[mid] ~ A[right] if A[mid] < target <= A[right] else, search left side
            """
            if nums[mid] >= nums[left]: # left rotated
                # in ascending order side
                if nums[left] <= target and target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else: # right rotated
                # in ascending order side
                if nums[mid] < target and target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        # cannot find the target value
        return -1

Upvotes: 2

Related Questions