33. Search in Rotated Sorted Array
Medium
You are given an integer array nums
sorted in ascending order, and an integer target
.
Suppose that nums
is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7]
might become [4,5,6,7,0,1,2]
).
If target
is found in the array return its index, otherwise, return -1
.
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
-10^4 <= nums[i] <= 10^4
- All values of
nums
are unique. nums
is guranteed to be rotated at some pivot.-10^4 <= target <= 10^4
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | class Solution { public int search(int[] nums, int target) { int n = nums.length, l = 0, r = n-1; while(l<=r){ int m = (l+r)/2; if(nums[m]==target) return m; if(target > nums[m]){ if(nums[0]>nums[n-1] && target>=nums[0] && nums[m]<=nums[n-1]){ r = m-1; }else{ l = m+1; } }else{//target<nums[m] if(nums[0]>nums[n-1] && nums[m]>=nums[0] && target<=nums[n-1]){ l = m+1; }else{ r = m-1; } } } return -1; } } |
No comments:
Post a Comment