代码模板
int l = -1, r = N;
while (l + 1 != r) // l和r为相邻的两个索引为止
{
int mid = l + r >> 1;
if (check(x)) l = mid;
else r = mid;
}
return l or r;
条件总结
- check(x): arr[mid] < x, l为最后一个小于x的索引, r为第一个大于等于x的索引
- check(x): arr[mid] <= x, l为最后一个小于等于x的索引, r为第一个大于x的索引
- 查找x的索引, arr[mid] < x则返回r, arr[mid] <= x则返回l