# 5. 两种写法对比

写法 1while(left <= right) 这种写法可以认为我们在循环体内部直接查找元素,把当前搜索区间分为三个部分。

程序开始的时候,我们对输入数组一无所知。

image.png{:style="width: 400px"}

我们选择 nums[mid] 的值看一下。

image.png{:style="width: 400px"}

如果中间位置的元素的值等于目标元素就直接返回。如果中间位置的元素不是目标元素,可以根据中间位置元素的值决定在中间位置的左边还是右边继续查找。这种查找方式把待搜索区间分为三个部分:左、中、右。

image.png{:style="width: 400px"}

重要经验:如果我们要找的元素性质非常明确、并且简单,通常这样写就可以。例如「力扣」第 704 题(二分查找 (opens new window)),第 633 题(平方数之和 (opens new window)

写法 2while(left < right) 这种写法表示在循环体内部排除元素,把当前搜索区间分为两个部分。

这种思路可以很形象地理解为「两边夹」,在解决复杂问题的时候,会使得思考的过程变得简单

程序开始的时候,我们对输入数组一无所知(这一步和写法 1 一样)。

image.png{:style="width: 400px"}

我们选择 nums[mid] 的值看一下(这一步和写法 1 一样)。

image.png{:style="width: 400px"}

然后我们只分析:在什么情况下,目标元素位于哪个区间里,把区间分成「一定不存在目标元素的区间」和「可能存在目标元素的区间」。而 mid 只可能位于这两个区间的其中一个,可以分为下面 4 种情况。

image.png{:style="width: 400px"}

虽然看起来比较多,但是归结起来就 2 种情况:mid 在左边区间和 mid 在右边区间。即:根据 mid 的值,可以判断 nums[mid] 是「一定不是目标元素」还是「有可能是目标元素」,进而判断 mid 的左右两边的区间的性质。

重要经验

如果我们要找的元素的性质比较复杂:例如需要满足「条件 1」并且「条件 2」。我们在编写 if 语句的时候,就可以把其中一个条件取反,就可以达到缩减搜索区间的目的。

这一点也不难想明白,「条件 1」并且「条件 2」的反面就是「取反条件 1」或者「取反条件 2」。再举一个具体的例子:例如我们要找一个数 ,需要满足 ,即 并且 。如果我们看到一个数小于 ,我们就知道此时需要在当前位置的右边继续查找,可以得到缩减问题区间的目的。

「力扣」第 4 题(寻找两个正序数组的中位数 (opens new window))的 视频题解 (opens new window),我们详细介绍了用这种思路分析问题的方法,并给出了 2 版等价的代码。