33. Search in Rotated Sorted Array
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
这一题和LeetCode Find Minimum in Rotated Sorted Array类似，只不过不是查找最小值，而是查找某个target是否存在。也是采用二分查找的思路，首先判断nums[m]和nums[r]的关系，如果nums[m]<nums[r]，说明右半部分是有序的，看看target是否在该部分范围内，如果在，则l=mid+1；否则r=mid-1。如果nums[m]>nums[r]，说明右半部分无序，则左半部分有序，看看target是否在左半部分范围内，如果在，则r=mid-1；否则l=mid+1。如此循环下去。
完整代码如下：
class Solution {
public:
int search(vector<int>& nums, int target)
{
int l = 0, r = nums.size() – 1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target)
return mid;
if (nums[mid] < nums[r]) {
if (target > nums[mid] && target <= nums[r]) {
l = mid + 1;
}
else {
r = mid – 1;
}
}
else {
if (target >= nums[l] && target < nums[mid]) {
r = mid – 1;
}
else {
l = mid + 1;
}
}
}
return -1;
}
};本代码提交AC，用时9MS。
二刷。用递归方法实现，每次判断区间的左边是否小于右边，如果是的话，说明是有序的，常规二分即可；如果不是，则取中点，递归在其左边和右边搜索。由于取了中点后，必定有一边是有序的，则要么在有序区间搜索，要么在另一边搜索，即每次是减半的，所以时间复杂度也是O(lgN)。
完整代码如下：
class Solution {
public:
int BinarySearch(vector<int>& nums, int target, int left, int right) {
if (left > right)return -1;
if (left == right) {
if (nums[left] == target)return left;
else return -1;
}
if (nums[left] < nums[right]) {
if (target >= nums[left] && target <= nums[right]) {
int mid = left + (right - left) / 2;
if (nums[mid] == target)return mid;
else if (nums[mid] < target)return BinarySearch(nums, target, mid + 1, right);
else return BinarySearch(nums, target, left, mid - 1);
}
else {
return -1;
}
}
else {
int mid = left + (right - left) / 2;
int lans = BinarySearch(nums, target, left, mid);
int rans = BinarySearch(nums, target, mid + 1, right);
if (lans != -1)return lans;
if (rans != -1)return rans;
return -1;
}
}
int search(vector<int>& nums, int target) {
return BinarySearch(nums, target, 0, nums.size() - 1);
}
};
本代码提交AC，用时0MS。
三刷。迭代方法还是主流，和常规二分搜索的代码框架是一致的。但是一刷的时候是先判断右半部分是否有序，有点不符合直觉，如果简单的先判断左半部分，会出bug，比如[3,1]，要找1的时候，此时m=0，和l=0是相同的，如果简单的用nums[l]<nums[m]来判断左边是否有序的话，会有问题，此时m==l，所以左边也可以看做是有序的，但不满足nums[l]<nums[s]。所以需要额外加一个l==m的判断。完整代码如下：
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while(l <= r) {
int m = l + (r - l) / 2;
if(nums[m] == target) return m;
if(l == m || nums[l] < nums[m]) { // l == m 左边只有一个元素，左边也是有序的
if(target >= nums[l] && target < nums[m]) r = m - 1;
else l = m + 1;
} else {
if(target > nums[m] && target <= nums[r]) l = m + 1;
else r = m - 1;
}
}
return -1;
}
};本代码提交AC， 用时8MS。
For example, the above binary watch reads “3:25”.
Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.
Example:
