搜索旋转排序数组(系列)
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
python语言
class Solution:
def search(self, nums: List[int], target: int) -> int:
low, high = 0, len(nums)-1
# 将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。
# 此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环.
while low <= high:
mid = low + (high-low)//2
print('low,high,mid', low, high, mid)
if nums[mid] == target:
return mid
elif nums[low] <= nums[mid]:
# 左半有序 且目标值在左部分
if nums[low] <= target < nums[mid]:
high = mid - 1
else:
low = mid + 1
else:
# 右半有序 且目标值在右部分
if nums[high] >= target > nums[mid]:
low = mid + 1
else:
high = mid - 1
return -1
go语言
go的执行效率比python真是高太多了
func search(nums []int, target int) int {
low, high := 0, len(nums)-1
// 将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。
// 此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环.
// fmt.Println(low, high)
// print(low, high)
for low <= high{
mid := low + (high-low)/2
// fmt.Println(low, mid, highc)
if nums[mid] == target{
return mid
}else if nums[low] <= nums[mid]{ //左半数组有序, 注意<=
if nums[low] <= target && target < nums[mid]{
high = mid - 1
}else{
low = mid + 1
}
}else{
if nums[high] >= target && target > nums[mid]{
low = mid + 1
}else{
high = mid - 1
}
}
// fmt.Println("-----", low, mid, high)
}
return -1
}C++
旋转后，每次二分的时候，一定会得到一半是有序一半是无序的数组，如果目标值落在有序部分，则可以按照经典二分处理，否则在无序部分再二分
class Solution {
public:
int search(vector<int>& nums, int target) {
int low = 0, high = nums.size()-1;
while (low <= high) {
int mid = low + (high-low)/2;
if (target == nums[mid]) {
return mid;
}else if (nums[low] <= nums[mid]) {
// 结果在左半边有序的这部分，注意包含左边界
if (nums[low] <= target && target < nums[mid]) {
high = mid - 1;
}else{
low = mid + 1;
}
}else{
// 结果在右半边有序的这部分，注意包含右边界
if (nums[mid] < target && target <= nums[high]) {
low = mid + 1;
}else{
high = mid - 1;
}
}
}
return -1;
}
};81. 搜索旋转排序数组 II
已知存在一个按非降序排列的整数数组 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
class Solution {
public:
int search(vector<int>& nums, int target) {
int low = 0, high = nums.size()-1;
while (low <= high) {
int mid = low + (high-low)/2;
if (target == nums[mid]) {
return true;
// 核心在于 如果有重复的数，可能导致无法判断哪边是有序的
}else if (nums[low] == nums[mid] && nums[high] == nums[mid]){
low++;
high--;
}else if (nums[low] <= nums[mid]) {
// 结果在左半边有序的这部分，注意包含左边界
if (nums[low] <= target && target <= nums[mid]) {
high = mid - 1;
}else{
low = mid + 1;
}
}else{
// 结果在右半边有序的这部分，注意包含右边界
if (nums[mid] <= target && target <= nums[high]) {
low = mid + 1;
}else{
high = mid - 1;
}
}
}
return false;
}
};153. 寻找旋转排序数组中的最小值
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到： 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2] 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7] 注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [3,4,5,1,2] 输出：1 解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。 示例 2：
输入：nums = [4,5,6,7,0,1,2] 输出：0 解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。 示例 3：
输入：nums = [11,13,15,17] 输出：11 解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
提示：
n == nums.length 1 <= n <= 5000 -5000 <= nums[i] <= 5000 nums 中的所有整数 互不相同 nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
class Solution {
public:
int findMin(vector<int>& nums) {
int ans = INT_MAX;
int left = 0, right = nums.size()-1;
while (left <= right) {
int mid = left + (right-left)/2;
// 左边有序，left即为左边最小值，需要去右边找
if (nums[left] <= nums[mid]) {
ans = min(ans, nums[left]);
left = mid + 1;
}else{
// 右边有序，mid即为右边最小值，需要去左边找
ans = min(ans, nums[mid]);
right = mid - 1;
}
}
// cout << left << " " << right << endl;
return ans;
}
};154. 寻找旋转排序数组中的最小值 II
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到： 若旋转 4 次，则可以得到 [4,5,6,7,0,1,4] 若旋转 7 次，则可以得到 [0,1,4,4,5,6,7] 注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须尽可能减少整个过程的操作步骤。
示例 1：
输入：nums = [1,3,5] 输出：1 示例 2：
输入：nums = [2,2,2,0,1] 输出：0
提示：
n == nums.length 1 <= n <= 5000 -5000 <= nums[i] <= 5000 nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
class Solution {
public:
int findMin(vector<int>& nums) {
int ans = INT_MAX;
int left = 0, right = nums.size()-1;
while (left <= right) {
int mid = left + (right-left)/2;
// 重复数字会导致无法判断左右哪边是否有序
if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
ans = min(ans, nums[mid]);
left++;
right--;
}else if (nums[left] <= nums[mid]) {
ans = min(ans, nums[left]);
left = mid + 1;
}else{
ans = min(ans, nums[mid]);
right = mid - 1;
}
}
return ans;
}
};还有一种逐渐逼近的思路，但是容易出错
class Solution {
public:
int findMin(vector<int>& nums) {
int ans = INT_MAX;
int left = 0, right = nums.size()-1;
while (left <= right) {
// 如果全局有序，直接返回
if (nums[left] < nums[right]) return nums[left];
int mid = left + (right-left)/2;
// 重复数字会导致无法判断左右哪边是否有序
if (nums[left] == nums[mid]) {
left++;
// 如果左边有序，由于全局无序，则右边必无序，最小值在右边
}else if (nums[left] < nums[mid]) {
left = mid + 1;
// 左边无序，右边有序，mid即为右边最小值
}else{
right = mid;
}
}
// cout << left << " " << right;
return nums[right];
}
};