Question-33
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[ k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2 ,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3 输出：-1
示例 3：
输入：nums = [1], target = 0 输出：-1
提示：
1 <= nums.length <= 5000 -10^4 <= nums[i] <= 10^4 nums 中的每个值都 独一无二 题目数据保证 nums 在预先未知的某个下标上进行了旋转 -10^4 <= target <= 10^4
进阶：你可以设计一个时间复杂度为 O(log n) 的解决方案吗？ Related Topics 数组 二分查找 👍 1623 👎 0
Answer-33
//33 //81\153\154
//[4,5,6,0,1,2,3]
//in：nums = [4,5,6,7,0,1,2], target = 0
//out：4
//O(log(n))
//中间值>最右边值，说明左侧有序；中间值<最右值，说明右侧有序。判断target是否在有序列首尾之间...
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size()-1;
// while (l < r) {
while (l <= r) {
int mid = (l+r)/2;
printf("nums[%d] = [%d]\n", mid, nums[mid]);
if (nums[mid] == target) return mid;
if (nums[mid] > nums[r]) {
if (nums[l] <= target && nums[mid] >= target) {
r = mid - 1;
} else {
l = mid + 1;
}
} else if (nums[mid] <= nums[r]){
if (nums[mid] <= target && nums[r] >= target) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return -1;
}
Question-81
已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1, 2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。
给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。
你必须尽可能减少整个操作步骤。
示例 1：
输入：nums = [2,5,6,0,0,1,2], target = 0 输出：true
示例 2：
输入：nums = [2,5,6,0,0,1,2], target = 3 输出：false
提示：
1 <= nums.length <= 5000 -10⁴ <= nums[i] <= 10⁴ 题目数据保证 nums 在预先未知的某个下标上进行了旋转 -10⁴ <= target <= 10⁴
进阶：
这是 搜索旋转排序数组 的延伸题目，本题中的 nums 可能包含重复元素。 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
Related Topics 数组 二分查找 👍 694 👎 0
Answer-81
/*
* 81
* in：nums = [2,5,6,0,0,1,2], target = 0
* out：true
* in：nums = [2,5,6,0,0,1,2], target = 3
* out：false
* nums 可能包含重复元素
*/
bool search_81(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 true;
if (nums[mid] < nums[r]) { //中间数<最右数，右边有序，[5,6,0,1,2,3,4]，1<4，12345有序
if (nums[mid] <= target && nums[r] >= target) {
l = mid + 1;
} else {
r = mid - 1;
}
} else if (nums[mid] > nums[r]) { //中间数>最右数, 左边有序, [2,5,6,7,0,1,2]，7>2，2567有序
if (nums[mid] >= target && nums[l] <= target) {
r = mid - 1;
} else {
l = mid + 1;
}
} else { //{1,0,1,1,1} target0 超时，nums可能包含重复元素，移动指针位置
if (nums[l] == target) return true;
l++;
// if (nums[r] == target) return true;
// r--;
}
}
return false;
}
