二分查找法理论

使用场景

若数据是有顺序的，且数据中无重复元素，需要查找元素，第一时间就应该想起二分查找法

这里的有顺序不是指必须按升序或降序的顺序排列。 非降序、非升序、或部分有序的情况也是适用的

方法原理

二分法有两种写法，主要区别在于区间的定义，一种是左闭右闭，即[left, right],另一种则是[left, right)

要在二分查找的过程中，在while寻找中每一次边界的处理都要坚持根据区间的定义来操作

这里以704. 二分查找为例说明：

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

示例：

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

1. 二分法写法1（左闭右闭）

```python class Solution: def search(self, nums: List[int], target: int) -> int: left, right = 0, len(nums) - 1 # 位置1

    while left <= right: # 位置2
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1 # 位置3
        else:
            return mid
    return -1 ```

2.二分法写法2（左闭右开）

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

总结：

1. 两种写法中，有3个位置写法不同
   • 位置1：定义区间，写法1定义左闭右闭区间，写法2定义左闭右开
   • 位置2：结束条件，写法1左右指针可以取到同一个值，写法2则取不到同一个值
   • 位置3：定义右区间界限，写法1右区间可以取到mid - 1，写法2则取不到mid
2. 注意mid计算时的写法，注意防止mid计算溢出，left + (right - left) / 2比(right + left) / 2更安全，且前者有效避免溢出
3. 对于向上或向下取整问题，可参考69. Sqrt(x)解答