Search in Rotated Sorted Array

Problem Statement: here

Solution:

• The array was originally sorted, but it has been rotated. But even after rotation, at least one side of the array will still be properly sorted always.
• 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. After finding the sorted side, check if the target lies within that range.
• If the target lies in that sorted part, continue searching there. If not, ignore that part and search in the other half. Keep repeating this process, 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