二分查找的细节问题

2022-02-08

二分查找，是面试的基本问题，很多困难的问题中也要用到这个技术。写code时，有些小细节，还是需要留心。不然就可能出错。

问题描述

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-search

示例1：

输入: nums = [-1,0,3,5,9,12], target = 9

输出: 4

解释: 9 出现在 nums 中并且下标为 4 示例2：

输入: nums = [-1,0,3,5,9,12], target = 2

输出: -1

解释: 2 不存在 nums 中因此返回 -1

代码实现

因为这个问题比较简单，这里先给出代码，然后针对代码中几个小细节进行分析说明。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        i = 0
        j = len(nums)
        while  i < j:
            mid = (i + j) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                i = mid+1
            else:
                j = mid
        
        return -1

细节分析

细节1 j的初始化值

代码中，j被初始化成了len(nums)。有的小伙伴可能看到不少二分查找中j是被初始化成len(nums)-1的。但是就这个实现版本来说，是不行的。举例来说：

[1,2,3,4,5]

target = 5

如果初始化成len(nums)-1，则无法找到目标值。显然是错误的。

细节2 while循环的条件

这里while循环的条件是 i<j。有的实现是i<=j。

但是就这个版本的代码而言，这样并不是不行。只是程序终止后，i有可能大于j。

使用本版的i<j，可以保证，循环终止后，i一定是等于j的。

这样，当我们需要进一步使用i和j的值时，省去了纠结用哪个的烦恼。

细节3 指针更新逻辑

可以看到，需要更新i时，代码使用了 i=mid + 1，但在需要更能j时，使用的是 j = mid。

这样的更新逻辑，目标也是为了确保循环终止后，i和j相等。

细节4 如果目标值不在数组中

如果目标值不在数组中，循环结束后，i和j会指向比目标值大一点的那个元素。

比如 数组是 [1,2,4]，目标是3，循环结束后，i和j会指向4。如果目标是5， 则i和j会等于3，这个index已经超出数组的范围，使用时需要留心一下。

感觉不确定的小伙伴，可以实际尝试一下。

总结

二分查找细节上可以做不同的处理，这些处理会导致一些细微的差异。我建议，熟悉一种版本的代码，并掌握其中的各种细节，能够灵活使用即可。