fix: 优化描述

lucifer · lucifer · commit 5fbabfc04169 · 2021-01-05T11:12:56.000+08:00
diff --git a/91/binary-search.md b/91/binary-search.md
@@ -380,6 +380,8 @@ function binarySearchRight(nums, target) {
 
 另外如果有多个满足条件的值，我们返回最左侧的。 比如一个数组 nums: [1,2,2,2,3,4]，target 是 2，我们应该插入的位置是 1。
 
+#### 思维框架
+
 不管是寻找最左插入位置还是后面的寻找最右插入位置，我们的更新指针代码都是一样的。即：
 
 ```
@@ -388,21 +390,38 @@ l = mid + 1
 r = mid
 ```
 
-当然也有别的方式（比如 mid 不是向下取整，而是向上取整）， 但是这样可以最小化记忆成本。
+> 当然也有别的方式（比如 mid 不是向下取整，而是向上取整）， 但是这样可以最小化记忆成本。
 
-#### 思维框架
+有的人有疑问，这样设置结束条件会不会漏过正确的解，必然是不会的，如果更新区间代码是 r = mid - 1 还有可能错过，而 r = mid 这种代码根本就没有摒弃 r。
+
+这样描述可能不够清晰。为了探究这个问题， 我们继续往下看。
+
+以 nums = [1,3,4], target = 2 为例。我们要找的其实就是 [1,x,3,4] 中 x 所在的位置，换句话说**我们的目的就是不断收缩搜索区间到 x 位置**。
+
+- 如果 nums[mid] < x，由于 nums 是单调增的，因此 mid 一定在 x 左侧，小于等于 mid 部分一定不是最终解，我们将 mid + 1 作为新的搜索区间的左区间。
+- 如果 nums[mid] >= x，由于 nums 是单调增的，因此 mid 一定在 x 的位置或者在 x 的右侧，由于 mid 可能就在 x 的位置，所以 r = mid - 1 就可能错过了这种解，使用 r = mid 这种更新方式可避免这种情况。
+
+说得再直白一点。假设使用最左插入位置的方式查找的索引 为 i，那么应该满足不等式 nums[i] >= target。
+
+- nums = [1,3,4], target = 2 的情况 i = 1，nums[i] = 3 > 2
+- nums = [1,2,2,2,3,4], target = 2 的情况 i = 1，nums[i] = 2 = 2
+
+因此
+
+- 如果 nums[mid] 已经小于 target 了，就必然是不可能的情况，直接通过 l = mid + 1 排除
+- 否则无法排除， 使用 r = mid 即可， mid 就是我们找到的一个备胎。
+
+具体算法：
 
 - 首先定义搜索区间为 [left, right]，注意是左右都闭合，之后会用到这个点。
 
 > 你可以定义别的搜索区间形式，不过后面的代码也相应要调整，感兴趣的可以试试别的搜索区间。
 
 - 由于我们定义的搜索区间为 [left, right]，因此当 left <= right 的时候，搜索区间都不为空。 但由于上面提到了更新条件有一个`r = mid`，因此如果结束条件是 left <= right 则会死循环。因此结束条件是 left < right。
 
-> 有的人有疑问，这样设置结束条件会不会漏过正确的解，其实不会。举个例子容易明白一点。 比如对于区间 [4,4]，其包含了一个元素 4，搜索区间不为空。如果我们的答案恰好是 4，会被错过么？不会，因为我们直接返回了 4。
-
 - 循环体内，我们不断计算 mid ，并将 nums[mid] 与 目标值比对。
-  - 如果 nums[mid] 大于等于目标值， r 也可能是目标解，r - 1 可能会错过解，因此我们使用 r = mid。
-  - 如果 nums[mid] 小于目标值， mid 以及 mid 左侧都不可能是解，因此我们使用 l = mid + 1。
+  - 如果 nums[mid] 大于等于目标值（mid 在 x 位置或者 x 的右侧）， r 也可能是目标解（等于的情况），r - 1 可能会错过解，因此我们使用 r = mid。
+  - 如果 nums[mid] 小于目标值（mid 在 x 的左侧）， mid 以及 mid 左侧都不可能是解，至少是 mid + 1 才行，因此我们使用 l = mid + 1。
 - 最后直接返回 l 或者 r 即可。（并且不需要像`最左满足条件的值`那样判断了）
 
 #### 代码模板
@@ -433,6 +452,8 @@ def bisect_left(nums, x):
 
 和`寻找最左插入位置`类似。不同的地方在于：如果有多个满足条件的值，我们返回最右侧的。 比如一个数组 nums: [1,2,2,2,3,4]，target 是 2，我们应该插入的位置是 4。
 
+具体算法：
+
 - 首先定义搜索区间为 [left, right]，注意是左右都闭合，之后会用到这个点。
 
 > 你可以定义别的搜索区间形式，不过后面的代码也相应要调整，感兴趣的可以试试别的搜索区间。
