Binary Search: Rotated Array

You are given an array of length $$n$$ that was originally sorted in ascending order, then rotated between 1 and $$n$$ times. Given the rotated sorted array nums and an integer target, return the index of target in nums, or -1 if it is not present. All elements are unique.

Answer

Before anything else, in the binary search loop we first check if nums[m] == target and return m immediately. The main idea then is: if nums[l] <= nums[m] the left half is sorted, so check whether target lies in $[\texttt{nums[l]}, \texttt{nums[m)})$ ; if yes, move right boundary left, otherwise search the right half. Else the right half is sorted; check whether target lies in $(\texttt{nums[m]}, \texttt{nums[r]}]$ ; if yes, move left boundary right, otherwise search the left half.

Method 1, Trivial $$O(n)$$ :

        for i in range(len(nums)):
            if nums[i] == target:
                return i
        return -1

Method 2, Binary Search $O(\log n)$ :

        l, r = 0, len(nums) - 1
        while l <= r:
            m = (l + r) // 2

            if nums[m] == target:
                return m

            if nums[l] <= nums[m]:  # left half sorted
                if nums[l] <= target < nums[m]:
                    r = m - 1
                else:
                    l = m + 1
            else:                   # right half sorted
                if nums[m] < target <= nums[r]:
                    l = m + 1
                else:
                    r = m - 1

        return -1