526互联

704. 二分查找

发布时间 2024-01-11 07:35:32作者: 我是球啊

首先我们读题抓住几个关键点：

1. 有序数组

2. 元素不重复

因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件。当大家看到题目满足如上条件时，可以想一想能不能使用二分法。

二分法非常重要的是边界条件，区间的定义就是不变量，要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。

写二分法，一般有两种定义，左闭右闭[left, right]，或者左闭右开即[letf, right)。

 

二分法第一种写法

第一种写法，我们定义target是一个在左闭右闭的区间里，也就是[left, right]。区间的定义决定了二分法的代码应该如何写，因为定义target在[left, right]区间，所以有如下两点：

  • while (left <= right)要使用<=，因为left==right是有意义的，所以使用<=
  • if (nums[middle] > target) right要赋值为middle - 1，因为当前这个nums[middle]-1一定不是target，那么接下来要查找的左区间结束下标位置就是middle - 1.

 写一下伪代码，寻找target：

left = 0

right = nums.size - 1

while (left <= right)

　　middle = (left+right) / 2 避免越界的话可以写 middle = left + (right - left) / 2

　　if (nums[middle] > target)

　　　　right = middle - 1

　　else if (nums[middle] < target)

　　　　left = middle + 1

　　else return middle

return -1

二分法的第二种写法

当区间变成左闭右开时，也就是[left, right)，那么二分法的边界处理方式截然不同。

有如下两点：

  • while (left < right)，这里用<，因为left==right在区间内没有意义
  • if (nums[middle] > target)，right更新为middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即，下一个查询区间不会去比较nums[middle]

left = 0

right = nums.size

while (left < right)

　　middle = (left+right) / 2 避免越界的话可以写 middle = left + (right - left) / 2

　　if (nums[middle] > target)

　　　　right = middle

　　else if (nums[middle] < target)

　　　　left = middle + 1

　　else return middle

return -1

接下来我们一起写一下两种版本的python代码吧！

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

此处需要进行round操作，否则数组index不为整数。

round是一个python函数，进行四舍五入取整，还可以指定想保留的小数位数。

round和//（整数除）还是有区别的。

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