Leetcode: Search in rotated array

Search in Rotated Sorted Array | LeetCode OJ

We have already seen how to search for an element in a sorted array. A rotated array will simply have an increasing sequence for till the highest element and then a drop followed by another increasing. To search in this array we can simply find the minimum element and search in the point at which the highest element and search for the element in either the left or right side of it.

We can identify the pivot element by comparing it to its neighbors. Both of them would be greater than it. So first we perform a binary search to find an element which satisfies this.

1. Find middle element of the list and compare it with its neighbors
2. If left is lower and right is higher we are in the ascending section of the list and the pivot is towards the smaller side i.e. left, otherwise it is to the right
3. For moving left, move the high pointer to mid
4. For moving right, move the left pointer to mid

Once we find the pivot, we can do a search on first element to pivot if the target lies in that range otherwise on pivot to last element.

Remarks:

1. O(log n) + O(log n) time complexity, for performing the binary search twice
2. O(1) space complexity as no new copies of the existing arrays are created

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if len(nums) == 1:
            return 0 if target == nums[0] else -1
        low = 1
        high = len(nums)
        mid = (low + high) / 2
        while nums[mid] > nums[mid - 1] and low != mid:
            if low == mid:
                mid = len(nums)
                break
            if nums[0] < nums[mid]:
                low = mid
            else:
                high = mid
            mid = (low + high) / 2
        # new array start at mid
        low, high = (0, mid) if target >= nums[0] and target <= nums[mid - 1] else (mid, len(nums))
        mid = (high + low) / 2
        while low != mid:
            if target == nums[mid]:
                return mid
            if target > nums[mid]:
                low = mid
            else:
                high = mid
            mid = (high + low) / 2
        return -1 if nums[low] != target else low