acwing算法基础之基础算法--整数二分算法

1 知识点

有单调性一定可以二分，但在某些情况下，不具有单调性也可以二分。
单调性也可以抽象成某类性质，分界点左边不满足此性质，而右边满足此性质。当然也可以分界点左边满足此性质，而右边不满足此性质。
注意存在边界情况，容易进入死循环，此时需要考虑[0,1]的case去设置mid。

2 代码模板

//有序向量nums
//请找到第一个大于等于x的下标，相当于lower_bound()
int l = 0, r = nums.size() - 1;
while (l < r) {int mid = l + r >> 1;if (nums[mid] >= x) { //找到第一个大于等于x的下标，相当于lower_bound()r = mid;} else {l = mid + 1;}
}
if (nums[l] == x) {cout << "pass" << endl;
} else {cout << "failed" << endl;
}

//有序向量nums
//请找到最后一个小于等于x的下标
int l = 0, r = nums.size() - 1;
while (l <= r) {int mid = l + r + 1 >> 1;if (nums[mid] <= x) {l = mid;} else {r = mid - 1;}
}
if (nums[l] == x) {cout << "pass" << endl;
} else {cout << "failed" << endl;
}