LeetCode·33. Search in Rotated Sorted Array
程序员文章站
2022-07-16 11:53:07
...
题目:
Suppose an array sorted in ascending order 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]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm’s runtime complexity must be in the order of O(log n).
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
思路:
二分查找,判断最左和中间值的关系分情况讨论。
代码:
class Solution {
public:
int search(vector<int>& nums, int target) {
int L = 0;
int R = nums.size()-1;
while(L <= R){
int mid = (L+R)/2;
if(nums[mid] == target)return mid;
if(nums[L] <= nums[mid]){
if(nums[L] <= target && nums[mid] > target)
R = mid-1;
else
L = mid+1;
}else{
if(nums[L] > target && nums[mid] < target)
L = mid+1;
else
R = mid-1;
}
}
return -1;
}
};
结果:
推荐阅读
-
【LeetCode】Two Sum & Two Sum II - Input array is sorted & Two Sum IV - Input is a BST
-
Convert Sorted Array to Binary Search Tree
-
【一天一道LeetCode】#26. Remove Duplicates from Sorted Array
-
LeetCode 33. Search in Rotated Sorted Array && 81. Search in Rotated Sorted Array II
-
Leetcode 33 Search in Rotated Sorted Array
-
LeetCode·33. Search in Rotated Sorted Array
-
leetcode 33. Search in Rotated Sorted Array
-
0033_Search in Rotated Sorted Array
-
Search in Rotated Sorted Array II
-
33. Search in Rotated Sorted Array