33.-search-in-rotated-sorted-array.md

33. Search in Rotated Sorted Array

• Medium

• There is an integer array nums sorted in ascending order (with distinct values).

  Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

  Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

  You must write an algorithm with O(log n) runtime complexity.

Analysis

What we have is two separated sorted arrays within the given array. Therefore we can do the normal Binary search within each array. The only thing to notice is how should we distinguish if we are in the correct array.

Now for example we have an array like this [ 7, 8, 9, 10, 14, 1, 2, 5, 6]

if we are looking for 8, then we are looking for it in the array [7, 8, 9, 10, 14]

If we are looking for 5, then we should be looking in the array [ 1, 2, 5, 6]

Therefore we can compart it to the nums[0] and see if the number is larger than or smaller than that. That way we will be able to where we should be looking at.

With that in mind, we can introduce the nums[ mid ] we would be using in the binary search. If nums[mid] and target are on the same side of nums[0], then we are looking at the correct array.

class Solution:
    def search(self, nums, target):
            lo, hi = 0, len(nums)

            while lo < hi:
                mid = (lo + hi) // 2

                if (nums[mid] < nums[0]) == ( target < nums[0]):
                    if (nums[mid] < target):
                        lo = mid + 1
                    elif (nums[mid] > target):
                        hi = mid
                    else:
                        return mid
                elif target < nums[0]:
                    lo = mid + 1
                else:
                    hi = mid

            return -1