P37. 二分搜索插入位置

https://algocasts.io/episodes/dlWbxGvA

在一个细节里绕不过弯 :thinking:

依照视频中的例子,有序数组中找不到目标值的情况下,游标 low 即为目标值插入的位置

但我怎么确定所有情况 low 下标都是正确的插入位置?

@archy.shawn

while 循环中的条件是 low <= high,另外 low 和 high 每次的更新是在 mid 的基础上 +1 / -1。因此如果退出 while 循环,那么 high 一定比 low 小 1。也就是 high 在 low 左边,并且与 low 相邻

数组 A: A[0], A[1], A[2], ..., A[i], A[i+1], ..., A[n-1]
                               high  low

high 此时所在的位置是 low 曾经待过的位置,low 会向右移动,说明了这个位置的数字小于 target,于是有:

A[high] < target

同理,low 现在所在位置是 high 曾经待过的位置,high 会继续向左移动,说明了这个位置的数字大于 target,于是有:

A[low] > target

两个关系合并起来就是:

A[high] < target < A[low]

也就是说,target 这个数字应该放在下标 high 后面一个位置。用下面两种方式来表示 target 的插入下标都是可以的:

1. high+1
2. low   // 因为 low 就在 high 右边一个位置,即 low = high + 1
1赞