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.
Test Cases
Input:
(int[]) nums = [4,5,6,7,0,1,2]
(int) target = 0
Output:
(int) 4
Input:
(int[]) nums = [4,5,6,7,0,1,2]
(int) target = 3
Output:
(int) -1
Solution
class Solution {
public:
int search(vector<int>& nums, int target) {
int low = 0, high = nums.size() - 1, mid;
while(low <= high) {
mid = low + (high-low)/2;
cout<<low<<" "<<mid<<" "<<high<<endl;
if (nums[mid] == target) return mid;
if (nums[low] <= nums[mid]) {
if (nums[low] <= target && target < nums[mid]) {
high = mid-1;
} else {
low = mid+1;
}
} else {
if (nums[mid] < target && target <= nums[high]) {
low = mid+1;
} else {
high = mid-1;
}
}
}
return -1;
}
};package search_in_rotated_sorted_array
func search(nums []int, target int) int {
low, high := 0, len(nums)-1
for low <= high {
mid := low + (high-low)/2
if nums[mid] == target {
return mid
}
if nums[low] <= nums[mid] {
if nums[low] <= target && target < nums[mid] {
high = mid-1
} else {
low = mid+1
}
} else {
if nums[mid] < target && target <= nums[high] {
low = mid+1
} else {
high = mid-1
}
}
}
return -1
}class Solution {
public int search(int[] nums, int target) {
int low = 0, high = nums.length-1;
while(low <= high) {
int mid = low + (high-low)/2;
if (nums[mid] == target) return mid;
if (nums[low] <= nums[mid]) {
if (nums[low] <= target && target < nums[mid]) {
high = mid-1;
} else {
low = mid+1;
}
} else {
if (nums[mid] < target && target <= nums[high]) {
low = mid+1;
} else {
high = mid-1;
}
}
}
return -1;
}
}class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums: return -1
l = len(nums)
ll, ul = 0, l-1
while ll <= ul:
m = (ll + ul) // 2
print(ll, m, ul)
if nums[m] == target:
return m
if nums[ll] <= nums[m]:
if nums[ll] <= target <= nums[m]:
ul = m - 1
else:
ll = m + 1
else:
if nums[m] <= target <= nums[ul]:
ll = m + 1
else:
ul = m - 1
return -1