CA 20 - Search in Rotated Sorted Array

Problem Statement: here

Solution:

• The array was originally sorted, but it has been rotated, so it looks broken. However, even after rotation, at any moment, at least one side of the array will still be properly sorted.
• So the idea is to keep looking at the middle element and use it to decide where to go next. First, check which side of the array is in correct order left or right. Once you identify the sorted side, check if the number you are searching for lies within that range.
• If the target lies in that sorted part, you continue searching there. If not, you ignore that part and search in the other half. You keep repeating this process, narrowing down the search space each time, until you find the target or run out of elements.
• Basically we use the sorted half to guide the search instead of checking every element.

def search(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        m = (l + r) // 2
        if nums[m] == target:
            return m
        if nums[l] <= nums[m]:
            if nums[l] <= target < nums[m]:
                r = m - 1
            else:
                l = m + 1
        else:
            if nums[m] < target <= nums[r]:
                l = m + 1
            else:
                r = m - 1
    return -1