Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:


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


Example 2:


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

Difficulty: interview

Starter code:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        

Solutions:
class Solution:
     def search(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         # left = 0
         # right = len(nums) - 1
         # while left <= right: 
         #     mid = int((left + right)/2)
         #     if nums[mid] == target: 
         #         return mid
         #     elif (nums[right] < target) or (nums[mid] > target and nums[right] > target):  
         #         right = mid - 1
         #     else: 
         #         left = mid + 1
         # return -1
         
         left = 0
         right = len(nums) - 1
         while left <= right: 
             mid = int((left + right)/2)
             if nums[mid] == target: 
                 return mid
             if (nums[left] < nums[mid]): 
                 if (target < nums[left]) or (target > nums[mid]): 
                     left = mid + 1
                 else: 
                     right = mid - 1
             elif (nums[left] > nums[mid]): 
                 if (target < nums[mid]) or (target >= nums[left]): 
                     right = mid - 1
                 else: 
                     left = mid + 1
             else: 
                 if nums[right] == target: 
                     return right
                 else: 
                     return -1
         return -1

class Solution:
     def search(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         l, r = 0, len(nums)-1
         while l <= r:
             mid = (l+r)//2
             if nums[mid] == target:
                 return mid
             elif nums[mid] >= nums[l]:
                 if nums[l] <= target < nums[mid]:
                     r = mid-1
                 else:
                     l = mid+1
             else:
                 if nums[mid] < target <= nums[r]:
                     l = mid+1
                 else:
                     r = mid-1
         return -1

class Solution:
     def search(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         length = len(nums)
         if length <= 0:
             return -1
         pivot = self.find_pivot(0, length-1, nums)
         print(pivot)
         search_index_A = self.binary_search(0, max(pivot-1, 0), nums, target)
         search_index_B = self.binary_search(pivot, length-1, nums, target)
         if search_index_A >= 0:
             return search_index_A
         elif search_index_B >= 0:
             return search_index_B
         else:
             return -1
     
     def find_pivot(self, left_ind, right_ind, nums):
         mid = left_ind + (right_ind - left_ind)//2
         if left_ind == right_ind:
             return left_ind
         elif nums[mid] < nums[mid-1]:
             return mid
         elif nums[right_ind] < nums[mid]:
             return self.find_pivot(mid+1, right_ind, nums)
         else:
             return self.find_pivot(left_ind, max(0,mid-1), nums)
     
     def binary_search(self, left_ind, right_ind, nums, target):
         mid = left_ind + (right_ind - left_ind)//2
         if nums[mid] == target:
             return mid
         elif left_ind == right_ind:
             return -1
         elif nums[mid] < target:
             return self.binary_search(mid+1, right_ind, nums, target)
         else:
             return self.binary_search(left_ind, max(left_ind,mid-1), nums, target)


class Solution:
     def search(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         left, right = 0, len(nums)-1
         while left <= right:
             mid = (left+right) // 2
             if nums[mid] == target:
                 return mid
             elif nums[mid] >= nums[left]:
                 if nums[left] <= target < nums[mid]:
                     right = mid-1
                 else:
                     left = mid+1
             else:
                 if nums[mid] < target <= nums[right]:
                     left = mid+1
                 else:
                     right = mid-1
         return -1


class Solution:
     def search(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         # if target in nums:
         #     return nums.index(target)
         # else:
         #     return -1
 
         low, high = 0, len(nums)-1
         while low < high:
             mid = (low+high)//2
             if nums[mid] > nums[high]:
                 low = mid+1
             else:
                 high = mid
         start = low
         low, high = 0, len(nums)-1
         while low <= high:
             mid = (low+high)//2
             realMid = (mid+start) % (len(nums))
             if nums[realMid] == target:
                 return realMid
             if target > nums[realMid]:
                 low = mid+1
             else:
                 high = mid-1
         return -1
         
                 


class Solution:
     def search_interval(self, start, end, nums, target):
         if start == end:
             if nums[start] == target:
                 return start
             else:
                 return -1
 
         size = end - start
         half = size // 2
         new_start_1 = start
         new_end_1 = start + half
         new_start_2 = start + half + 1
         new_end_2 = end
 
         # check first interval
         first_half_sorted = False
         first_half_contains = False
         second_half_sorted = False
         second_half_contains = False
         if nums[new_end_1] >= nums[new_start_1]:
             first_half_sorted = True
             if (target >= nums[new_start_1]) and (target <= nums[new_end_1]):
                 first_half_contains = True
         if nums[new_end_2] >= nums[new_start_2]:
             second_half_sorted = True
             if (target >= nums[new_start_2]) and (target <= nums[new_end_2]):
                 second_half_contains = True
             
         if first_half_contains:
             return self.search_interval(new_start_1, new_end_1, nums, target)
         elif second_half_contains:
             return self.search_interval(new_start_2, new_end_2, nums, target)
         elif first_half_sorted:
             return self.search_interval(new_start_2, new_end_2, nums, target)
         elif second_half_sorted:
             return self.search_interval(new_start_1, new_end_1, nums, target)
 
     def search(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         
         if len(nums) == 0:
             return -1
 
         return self.search_interval(0, len(nums) - 1, nums, target)

class Solution:
     def search(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         length = len(nums)
         if length <= 0:
             return -1
         pivot = self.find_pivot(0, length-1, nums)
         print(pivot)
         search_index_A = self.binary_search(0, max(pivot-1, 0), nums, target)
         search_index_B = self.binary_search(pivot, length-1, nums, target)
         if search_index_A >= 0:
             return search_index_A
         elif search_index_B >= 0:
             return search_index_B
         else:
             return -1
     
     def find_pivot(self, left_ind, right_ind, nums):
         mid = left_ind + (right_ind - left_ind)//2
         if left_ind == right_ind:
             return left_ind
         elif nums[mid] < nums[mid-1]:
             return mid
         elif nums[right_ind] < nums[mid]:
             return self.find_pivot(mid+1, right_ind, nums)
         else:
             return self.find_pivot(left_ind, max(0,mid-1), nums)
     
     def binary_search(self, left_ind, right_ind, nums, target):
         mid = left_ind + (right_ind - left_ind)//2
         print(nums)
         print(mid)
         if nums[mid] == target:
             return mid
         elif left_ind == right_ind:
             return -1
         elif nums[mid] < target:
             return self.binary_search(mid+1, right_ind, nums, target)
         else:
             return self.binary_search(left_ind, max(left_ind,mid-1), nums, target)
 
 # [5,1,3]
 # [0]
 
 # find_pivot(0,2,[5,1,3])
 # left = 0
 # right = 2
 # mid = 0 + 2//2 = 1
 # nums[mid] < nums[mid-1]
 # pivot = 1
 # binary_search(0, max(pivot-1,0), ...)
 # left = 0, right = 0
 # search_index_A = -1
 # binary_search(pivot, length-1, ...)
 # left = 1, right = 2
 # mid = 1 + (2-1)//2 = 1
 # binary_search(1, max(0,0), ...)
 # search_index_B = -1


class Solution:
     def search(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         idx = -1
         for i in range(1,len(nums)):
             if nums[i] < nums[i-1]:
                 idx = i
                 break
         if idx == -1:
             return self.bin_search(nums, 0, len(nums), target)
         else:
             if target < nums[0] or target < nums[-1]:
                 return self.bin_search(nums, idx, len(nums), target)
             elif target > nums[-1] or target > nums[0]:
                 return self.bin_search(nums, 0, idx,  target)
             else: 
                 assert(False)
             
     def bin_search(self, nums, i1, i2, target):
         while i1 < i2:
             mi = (i1 + i2) // 2
             if nums[mi] == target: return mi
             if nums[mi] > target: i2 = mi
             else: i1 = mi + 1
         
         return -1


class Solution:
     def search(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         for i in range(0,len(nums)):
             if nums[i] == target:
                 return i
         return -1

class Solution:
     def search(self, nums, target):
         if len(nums) <= 3: return nums.index(target) if target in nums else -1
         l, r = 0, len(nums) - 1
         while l < r:
             m = (l + r) // 2
             left = nums[l]
             mid = nums[m]
             right = nums[r]
             if left == target:
                 return l
             if mid == target:
                 return m
             if right == target:
                 return r
             elif left < right:
                 print(('mono:', l, r))
                 if mid < target:
                     l = m
                     r -= 1
                 else:
                     r = m
                     l += 1
             else:
                 print(('not mono:', l, r))
                 if left < target < mid or mid < left < target or target < mid < left:
                     r = m
                     l += 1
                 else:
                     l = m
                     r -= 1
         return -1


class Solution:
     def search(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         low = 0
         high = len(nums)-1
         while high >= low:
             mid = high+low//2
             if nums[mid] == target:
                 return mid
             elif nums[mid] > nums[high]:
                 low = mid+1
             else:
                 print ("comes here")
                 print (high)
                 print (mid)
                 print (low)
                 high = mid-1
                 print (high)
         return -1


class Solution:
     def search(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         if not nums:
             return -1
         
         # [4,5,6,7,0,1,2]
         # 0
         start, end = 0, len(nums) - 1
         while start + 1 < end:
             mid = start + (end - start) // 2
             if target < nums[end]:
                 if nums[mid] < target or nums[mid] > nums[end]:
                     start = mid
                 elif nums[mid] > target and nums[mid] < nums[end]:
                     end = mid
                 else:
                     return mid
             elif target > nums[end]:
                 if nums[mid] > target or nums[mid] < nums[end]:
                     end = mid
                 elif nums[mid] < target and nums[mid] > nums[end]:
                     start = mid
                 else:
                     return mid
             else:
                 return len(nums) - 1
         
         if nums[start] == target:
             return start
         if nums[end] == target:
             return end
         
         return -1