关于二分查找:你真的懂二分查找吗

6次阅读

共计 1750 个字符，预计需要花费 5 分钟才能阅读完成。

二分查找是根本的、常见的算法，大家徒手写应该不成问题。面试中经常出现, 特地是面试官想给你送分的时候。但大多数时候大家的二分查找写法其实在面试官看来仅仅是及格。
大家可能会想，二分查找能玩出什么花色来？明天，咱们一起来看。
本文常识要求：会看图，会识字。

话不多说，间接看 leetcode 原题。leetcode704

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，写一个函数搜寻 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 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
提醒：
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间

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

上面是最常见的实现版本，咱们后续称之为版本 A.

func searchA(nums []int, target int) int {lo, hi := 0, len(nums) // 在左闭右开区间[lo, hi) 查找 target
    var mid int
    var midVal int
    for lo < hi { // 最初退出时，[lo,hi）区间为空
        mid = (lo + hi) / 2 // 两头索引
        midVal = nums[mid]
        if midVal == target {return mid} else if target < midVal {hi = mid} else { // midVal < target
            lo = lo + 1
        }
    }

    return -1
}

该算法工夫复杂度为 O(Nlogn), n 为数组长度，N 为系数。咱们的指标是：是否让 N 小一些。
咱们看下面的版本 A 实现，发现每次循环中，通过 nums[mid]，通过 2 次比拟，将数组分为三局部。如下图所示。

其实，咱们能够将 nums[mid] 和 nums[mid+1, hi) 合并为一个区间，这个区间的元素满足 >= target。这样做的目标是将比拟次数优化为 1.
退出区间时，hi = lo+1, 区间 [lo,hi) 仅有一个元素

(可能会对这个优化的意义产生疑难。如果咱们的数组不是整数，而是长字符串呢？)
1 次比拟，划分为 2 个区间示意图。
此时算法实现如下，咱们称之为版本 B。

func searchB(nums []int, target int) int {lo, hi := 0, len(nums) // 在左闭右开区间[lo, hi) 查找 target
    var mid int
    var midVal int
    for 1 < hi-lo { // 最初退出时，[lo,hi）区间仅有一个元素
        mid = (lo + hi) / 2 // 两头索引
        midVal = nums[mid]
        if target < midVal {hi = mid} else { // midVal <= target
            lo = lo + 1
        }
    }

    if nums[lo] == target {return lo}

    return -1
}

<1> 如果数组中有指标元素反复，是否返回最初面的索引
比方要删除数组中一个指标元素，删除最初地位的指标元素，数组挪动最小
<2> 如果数组中没有指标元素，是否返回能够插入的索引，而不是简略的 -1
这个地位从语义上说是：小于 target 的最初一个元素的下一个地位
这两个问题对咱们的返回值提出了更高的要求。好难啊？！不要怕，其实思路咱们之前曾经见过了。
关键点在于退出时 lo,hi 的语义(lo=hi, 且 lo 为符合要求地位的前面一个地位)

func searchC(nums []int, target int) int {lo, hi := 0, len(nums) // 在左闭右开区间[lo, hi) 查找 target
    var mid int
    var midVal int
    for 0 < hi-lo { // 最初退出时，[lo,hi）区间为空
        mid = (lo + hi) / 2 // 两头索引
        midVal = nums[mid]
        if target < midVal {hi = mid} else { //  midVal <= target
            lo = mid + 1
        }
    }

    return lo - 1
}

正文完