Leetcode 33. ( Search in Rotated Sorted Array )

In time, you will call me master -- Star Wars
https://leetcode.com/problems/search-in-rotated-sorted-array/

Description :

given a sorted array rotated one time sat a pivot point

given a target

find target index

return -1 if not found

Example :

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
nums = [4,5,6,7,0,1,2], target = 3
Output : -1

Soltuion:

index0123456origin0124567given4567012

method : view given rotated array as origin array without rotation

first use binary search to find rotate pivot point ( smallest point in given array )we find 0 in the given array, and index is 4 ( rotation = 4 )do binary search againadd a new variable realmid (mid + rotation = 4) % length => origin middle pointfor example :lo = 0 hi = 6 mid = 3 realmid = index : 0 (7%7) val : 4 (origin middle point)

code

class Solution:  """  @param A: an integer rotated sorted array  @param target: an integer to be searched  @return: an integer  """  def search(self, A, target):      # write your code here      lo = 0      hi = len(A)-1      if len(A) == 0:          return -1      # binary search find smallest      # we need to find smallest -- >       # which is the pivot point of the rotated list      # so if mid value > hi value -- >       # we need to go to left side of mid to keep searching samllest value      # if mid value < hi value -- >       # we need to go to right side of mid to keep searching smallest value      while lo < hi :          mid = lo + (hi-lo)//2          print(mid)          if A[mid] > A[hi]:              lo = mid +1           else:              hi = mid       # here lo == hi == rotate point == smallest value index      rot = lo      print("rot", rot)      lo = 0      hi = len(A)-1      # do binary search again to the rotate list       # and use rot to find origin middle point      while lo <= hi:          mid = (lo+hi)//2          realmid = (mid + rot) % len(A)          print(A[realmid], realmid)          if A[realmid] == target :              return realmid          if A[realmid] < target:              lo = mid + 1          else:              hi = mid - 1      print(lo,mid , hi)      return -1