算法12、基础二分查找的运用(旋转数组专题)
🌰1、旋转数组1-严格递增
晴问算法
由严格递增序列形成的旋转数组,它的特点是:
一直严格递增,突然递减了一个元素,然后又严格递增。比如 3 5 8 1 2
把它分为两半,就分别都是严格递增的子数组,3 5 8和1 2, 索引范围(查找区间初值)分别是【0, 2】,【3,4】
然后分别进行二分查找,若第一组找到了就直接返回mid, 不需要进行第二组的查找了。
注意:旋转数组也有可能依然严格递增
#include <iostream>
using namespace std;
const int MAXN = 100005;
int nums[MAXN], x, n;
int binaryXsearch(int start, int end){
int left = start, right = end, mid;
while(left <= right){
mid = (left + right) / 2;
if(nums[mid] == x)
return mid;
if(nums[mid] < x)
left = mid + 1;
if(x < nums[mid])
right = mid - 1;
}
if(left > right)
return -1;
}
int main(){
cin >> n >> x;
int special = -1;
//遍添加元素边找到旋转点
for(int i = 0; i < n; i++){
cin >> nums[i];
if(i >= 1 && nums[i-1] > nums[i] )
special = i;
}
//若未旋转直接对整个数组查找,并结束main函数:
if(special == -1){//说明旋转数组依然严格递增
printf("%d\n", binaryXsearch(0, n-1));
return 0;
}
//若旋转了,则分为两组严格递增的子数组:
int ans = binaryXsearch(0, special-1);
if(ans == -1)//如果第一组没找到就继续第二组寻找。
ans = binaryXsearch(special, n-1);
printf("%d\n", ans);
return 0;
}
🌰2、旋转数组2-非严格递增
晴问算法
依然将旋转数组分为两半非严格递增的子数组,找到旋转点即第一个小于等于前一个的元素
然后分别执行非严格递增序列寻找第一个某元素的思路:算法11、基础二分查找(寻找满足条件的元素专题)-CSDN博客🌰3、变体1-寻找第一个元素x
转化为寻找第一个大于等于元素x的下标,若返回的下标小于n且其元素等于x(下标从0开始)说明有解,否则无解打印-1.
#include <iostream>
using namespace std;
const int MAXN = 100005;
int nums[MAXN], x, n;
// 二分查找:寻找第一个大于等于 x 的位置
int binarySearch(int start, int end) {
int left = start, right = end + 1; // 注意右边界设置为 end + 1
while (left < right) { // 循环条件为 left < right
int mid = (left + right) / 2;
if (nums[mid] >= x) // 如果满足条件,收缩右边界
right = mid;
else
left = mid + 1; // 否则收缩左边界
}
return left; // left 是第一个符合条件的位置
}
int main() {
cin >> n >> x;
int spin = -1;
// 找到旋转点(第一个小于等于前一个的元素位置)
for (int i = 0; i < n; i++) {
cin >> nums[i];
if (nums[i] < nums[i - 1] && spin == -1) {
spin = i;
}
}
// 如果没有找到旋转点,则整个数组是非严格递增的
if (spin == -1) {
int ans = binarySearch(0, n - 1); // 整个数组执行二分查找
if (ans < n && nums[ans] == x)
cout << ans << endl;
else
cout << -1 << endl;
return 0;
}
// 存在旋转点,分别对两部分执行二分查找
int ans = binarySearch(0, spin - 1); // 前半部分
if (ans >= spin || nums[ans] != x) // 如果前半部分未找到,查找后半部分
ans = binarySearch(spin, n - 1);
if (ans < n && nums[ans] == x)
cout << ans << endl;
else
cout << -1 << endl;
return 0;
}
🌰3、旋转数组最小值1-严格递增
晴问算法
不使用二分法直接遍历循环:
int main(){
cin >> n;
int special = 0;
//边添加元素边找到旋转点,即第一个小于前一个元素的元素
for(int i = 0; i < n; i++){
cin >> nums[i];
if(i >= 1 && special == 0 && nums[i-1] > nums[i] )
special = i;
}
printf("%d\n", nums[special]);
}
🙀难-使用二分查找法:
由严格递增序列形成的旋转数组,它的最小点就是旋转点,以旋转点为界,它的左半部和右半部(把旋转点归到右半部)都严格递增,且左半部的元素都比右半部大。
初始状态:left = 0,right = n - 1,mid = (left + right) / 2。
1️⃣查找移动思路:
对于二分查找闭区间[left, right]:
记住二分查找的本质是不断缩小区间去逼近解,因此如果解存在则解一定在二分查找区间里。
若nums[mid] < nums[right],说明mid有可能是解,且若mid不是解,解应该在左半[left, mid]区间,反证:
假设旋转点在[mid, right]区间,则nums[mid]应该>=nums[right], 因为旋转点左侧的元素大于所有右侧的元素,与nums[mid] < nums[right]相悖。因此应该让right = mid。
若nums[mid] >= nums[right], 说明mid不是解,且旋转点一定在[mid+1, right]区间,反证:
假设旋转点不在[mid+1, right]区间,则该区间应该严格递增,即nums[mid]应该小于nums[right]。因此应该让left = mid + 1;
2️⃣特别注意⚠️-int除法的特性:
比如left == 2, right = 3, 则(left + right)/ 2 = 2, 所以除了left==right的情况, mid只可能等于left(当right=left+1时), 而不可能等于right, 因此,nums[mid] >= nums[right]的比较条件可以不要等号。
也因为int除法的此特性,该题建议让nums[mid]与nums[right]比较,而不是与nums[left]比较!!因为这样left == right就无法作为找到解的唯一标识了。
当left == right ,找到解了,结束循环。
#include <iostream>
using namespace std;
const int MAXN = 100000;
int n, nums[MAXN];
int findMin(){
int left = 0, right = n-1, mid;
while(left < right){
mid = (left + right) / 2;
if(nums[mid] < nums[right])
right = mid;
else
left = mid + 1;
}
return nums[left]; //or right;
}
int main(){
cin >> n;
for(int i = 0; i < n; i++)
cin >> nums[i];
printf("%d\n", findMin());
}