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:

  index	0	1	2	3	4	5	6
  origin	0	1	2	4	5	6	7
  given	4	5	6	7	0	1	2

• 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 again
  • add a new variable realmid (mid + rotation = 4) % length => origin middle point
    • for 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