二分查找一定要序列单调,保证左边一定比key
小(大),右边一定比key
大(小)
找到最大的比key
小的数
while (l < r)
{
int mid = l + r + 1 >> 1;
if (a[mid] < key) l = mid;
else r = mid - 1;
}
找到不大于key
的最大数
while (l < r)
{
int mid = l + r + 1 >> 1;
if (a[mid] <= key) l = mid;
else r = mid - 1;
}
找到最小比key
大的数
while (l < r)
{
int mid = l + r >> 1;
if (a[mid] <= key) l = mid + 1;
else r = mid;
}
找到不小于key
的最小数
while (l < r)
{
int mid = l + r >> 1;
if (a[mid] < key) l = mid + 1;
else r = mid;
}
结论:
本质在于if(check())
的判断与l
, r
的更新,要根据实际情况转换成左右两边(l ~ mid ~ r
)如何选择