Search In Rotated Sorted Array Problem: 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 :
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Table of Contents
Search In Rotated Sorted Array Problem Solution
Problem Solution In Python
class Solution:
def search(self, nums, target):
def search(nums, l, r):
m = (l + r) // 2
if nums[m] == target:
return m
if l == r:
return -1
if nums[l] < nums[m]:
if target >= nums[l] and target < nums[m]:
return search(nums, l, m - 1)
else:
return search(nums, m + 1, r)
elif r - m == 1:
if nums[r] == target:
return r
else:
return search(nums, l, m)
elif nums[m + 1] < nums[r]:
if target >= nums[m + 1] and target <= nums[r]:
return search(nums, m + 1, r)
else:
return search(nums, l, m - 1)
return -1
return -1 if not nums else search(nums, 0, len(nums) - 1)
Problem Solution In Java
class Solution {
public int search(int[] nums, int target) {
if(nums.length == 1){
return nums[0] == target ? 0 : -1;
}
int i=0;
int j = nums.length-1;
while(i<j){
if(nums[i] == target){
return i;
}
else if(nums[j] == target){
return j;
}
else if(target > nums[i]){
i++;
}
else{
j--;
}
}
return -1;
}
}
Problem Solution In C++
class Solution {
public:
int b_Search(vector<int>& nums, int target, int low, int high) {
while(low <= high) {
int mid = low + (high - low) / 2;
if(nums[mid] == target) return mid;
else if(nums[mid] > target) high = mid - 1;
else low = mid + 1;
}
return -1;
}
int search(vector<int>& nums, int target) {
int i = 0;
for(; i < nums.size() - 1; i++) {
if(nums[i] > nums[i + 1]) break;
}
int ans = b_Search(nums, target, 0, i);
if(ans != -1 || i == nums.size() - 1) return ans;
ans = b_Search(nums, target, i+1, nums.size() - 1);
return ans;
}
};
Problem Solution In C
int search(int* nums, int numsSize, int target){
int i = 0;
for(i = 0;i<numsSize;i++)
{
if((nums[i] == target) )
return i;
if((nums[numsSize - i-1] == target ))
return (numsSize-i-1);
}
return -1;
}