There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly left rotated at an unknown 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 left rotated by 3 indices 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] <= 104nums are unique.nums is an ascending array that is possibly rotated.-104 <= target <= 104class Solution {
public:
int search(vector<int>& nums, int target) {
if(nums.size()==1)
return nums[0]==target?0:-1;
int lt=0, rt=nums.size()-1, mid;
while(lt<=rt){
mid = lt+(rt-lt)/2;
// cout << lt << mid << rt << endl;
if(nums[mid]==target)
return mid;
if(nums[mid]>nums[lt]){ // lt -> mid sorted
if(nums[lt]==target)
return lt;
if(target>nums[lt] && target<nums[mid]) // do normal binary search
rt = mid-1;
else lt = mid+1; // skewed binary search again
} else { // mid is beyond pivot from lt
if(nums[rt]==target)
return rt;
if(target<nums[rt] && target>nums[mid]) // do normal binary search
lt = mid+1;
else rt = mid-1; // skewed binary search again
}
}
return -1;
}
};class Solution {
public int search(int[] nums, int target) {
int n = nums.length, lt = 0, rt = n - 1;
while (lt <= rt) {
int mid = lt + (rt - lt) / 2;
if (target == nums[mid])
return mid;
else if (nums[lt] <= nums[mid]) {
if (target >= nums[lt] && target < nums[mid]) {
rt = mid - 1;
} else {
lt = mid + 1;
}
} else {
if (target >= nums[mid] && target <= nums[rt]) {
lt = mid + 1;
} else {
rt = mid - 1;
}
}
}
return -1;
}
}