0. 下面【1】使用了类,【2】使用了函数
解析:
- 因为我们的代码中不存在l = mid+1;r = mid -1;这种可能会【跨越另一个指针】的情况,所以我们while条件写l+1!=r,言下之意,彼时你俩相差为1,我们就跳出循环了。
- 跳出时存在两种情况1:r指向的就是答案,2:没有答案,连r指向的都不是答案。
- 为什么最后检查 r 而不是 l?
- 在循环结束时,r 总是指向可能的解。L始终指向小于其索引的元素,而 r 指向大于或等于其索引的第一个元素。
- 因此,如果存在满足条件的元素,它一定在 r 的位置
- 这种算法特别适用于已排序且元素唯一的数组,其中我们要找的是第一个等于其索引的元素。
- 这段代码通过二分查找的思路,可以高效 【它的时间复杂度是 O(log n),比从头到尾遍历效率高多了】地找到了有序向量中第一个(元素本身等于其下标的元素,比如这个题中的3等于其下标3)
- 你可能会遇到的死循环风险: 如果你使用 l < r 作为循环条件,当 l 和 r 相邻时(即 l+1 == r),循环仍然会继续。因为 mid 的值始终会在 l 和 r 之间反复切换,无法收敛。
- 无法处理相邻元素的情况: 当目标元素恰好位于 l 和 r 之间时,使用 l < r 的条件会导致无法找到目标元素。
1.
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:int fun(vector<int>& nums) {int l = -1, r = nums.size();while (l + 1 != r) {int mid = l + r >> 1;if (nums[mid] < mid)l = mid;else r = mid;}if (nums[r] == r)cout << "find the pos is" << r;else cout << "-1";cout << endl;return 0;}
};int main() {Solution s;vector<int> vec{ -3,-1,1,3,5 };s.fun(vec);
}
2.
#include<vector>
#include<iostream>
using namespace std;
int main(){vector<int> vec{ -3,-1,1,3,5 };int l = -1, r = vec.size();while (l+1!=r) {int mid = (l+r)/2;if (vec[mid] < mid) {l = mid;}else {r = mid;}}if (vec[r] == r) {cout << "找到了,下标是" << r << endl;}else {cout << "没有找到" << endl;}
}