Question:
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.
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
Example 3:
Input: nums = [1], target = 0
Output: -1
Constraints:
1 <= nums.length <= 5000
-104 <= nums[i] <= 104
All values of nums are unique.
nums is an ascending array that is possibly rotated.
-104 <= target <= 104
My Code:
class Solution(object):
def search(self, arr, x):
l=0
u=len(arr)-1
m=0
while(l<=u):
m=(u+l)//2
if(arr[m]==x):
return m
elif(arr[m]<x):
l=m+1
else:
u=m-1
return -1
You can use binary-search but you need to consider that the array of the problem is not sorted (sorted but rotated) and you need to find the sorted part of the array on the left or right of middle.
class Solution:
def search(self, arr, x):
l=0
u=len(arr)-1
m=0
while l<=u :
m = l+(u-l)//2
if arr[m] == x :
return m
elif arr[m] >= arr[l] :
# sorted part is left-side of middle
if x >= arr[l] and x < arr[m]:
u = m-1
# sorted part is right-side of middle
else:
l = m+1
else:
# sorted part is right-side of middle
if x <= arr[u] and x > arr[m]:
l = m+1
# sorted part is left-side of middle
else:
u = m-1
return -1
Check:
>>> Solution().search([4,5,6,7,0,1,2], 0)
4
>>> Solution().search([4,5,6,7,0,1,2], 3)
-1
>>> Solution().search([1], 0)
-1