LeetCode has a Medium coding Problem in Its’ Algorithm Section “Search in Rotated Sorted Array”. Today We are going to solve this problem. LeetCode Link of the Problem is HERE
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
1 <= k < nums.length) such that the resulting array is
[nums[k], nums[k+1], ..., nums[n-1], nums, nums, ..., nums[k-1]] (0-indexed). For example,
[0,1,2,4,5,6,7] might be rotated at pivot index
3 and become
Given the array
nums after the possible rotation and an integer
target, return the index of
target if it is in
-1 if it is not in
You must write an algorithm with
O(log n) runtime complexity.
Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4
Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1
Input: nums = , target = 0 Output: -1
1 <= nums.length <= 5000
-104 <= nums[i] <= 104
- All values of
numsis an ascending array that is possibly rotated.
-104 <= target <= 104
Solution to Search in Rotated Sorted Array
class Solution(object): def search(self, nums, target): """ :type nums: List[int] :type target: int :rtype: int """
If you find the target value in the array return its index, otherwise return -1. You may assume no duplicate exists in the array.
class Solution: def search(self, nums, target): l, r = 0, len(nums)-1 while l <= r: mid = l + (r-l)//2 if nums[mid] == target: return mid if nums[l] <= nums[mid]: # here should include "==" case 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
Python-related posts Visit HERE
C++ related posts Visit HERE
Databases related posts Visit HERE
Data Structures related posts visit HERE
Algorithms related posts visit HERE
Data Science related posts visit HERE