二分查找

二分查找讲解

34

以后采用的版本，左右开区间

  1. while循环里面的condition是 left + 1 < right
  2. 更新左右区间都是 right or left = mid
  3. 返回 right

不同类型统一化处理

以上是处理 >= 的情况

就是对应这个图里面的right和left找区间

最关键的是区间外是什么范围

test
test2

补充

Arrays.binarySearch 的工作方式：

  1. 如果数组中存在目标值：
    • 返回目标值的索引（i >= 0）。
  2. 如果数组中不存在目标值：
    • 返回插入点的负数减一（即 -(插入点) - 1）。
    • 这个“插入点”是指目标值在数组中保持排序的位置。

2024-12-17

更多的例题

题目 2300
咋一眼没看出来可以用二分
二分的应用条件：

  1. 有序（sort（Array））
  2. 有>=的条件，或者等价的条件

这道题目是 xy > value的形式，可以转化为 y > value/x，接着使用二分来解决

原文的题目截图暂未保留。