乐趣区

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

1. 整体阐明

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

2. 最简略的二分查找

话不多说,间接看 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
}

3. 这么简略的算法还能优化吗?

该算法工夫复杂度为 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
}

4. 感动面试官

<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
}
退出移动版