查找算法是在查找表中找到key等于给定值的算法，主要有顺序，二分，插值查找等，还有利用树结构的树查找和散列表的hash查找。二分查找用的最多，重点复习二分查找。 平均查找长度（Average Search Length，ASL）：和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度（这个概念只在效率分析的时候有用）。

顺序查找

顺序查找就是无脑扫描一遍，然后对每个元素和key进行比较，如相同则找到，扫描结束也没有找到即为查找失败。（这个真的很简单）

二分查找

二分查找需要查找表是有序的，让给定key和中间节点比较，中间节点把要查找的元素分成两半。如LeetCode 69.求解sqrt(n)的近似整数解。

class Solution_69:
    def mySqrt(self, x: int) -> int:
        lo = 0
        hi = x // 2 + 1
        while lo <= hi:
            mid = (lo + hi) >> 1
            t = mid * mid
            if t == x:
                return mid
            elif t < x:
                lo = mid + 1
            else:
                hi = mid - 1
        return hi

上述代码就是典型的二分查找的框架，代码本身很简单，不过中间有一些点值得注意：

循环的终止条件和更新左右边界相关, lo<=hi/lo<hi对应于取中间节点（mid是否+/-1），否则很容易随手写一个死循环，不过这个错误很容易通过测试查出来。

mid = (lo + hi) // 2 在python中，整数不会溢出这样不会有问题，在C++中，有可能lo+hi的值超出了32位整数表示范围，会产生错误，所以衍生出了几个写法

int mid = (lo + hi) / 2;       // C++ int/int = int ,python 要用整数除运算符 `//`
int mid = (lo + hi) >> 1;
int mid = lo + (hi - lo) / 2;  // 后面两个最安全的, 不过注意python3中
int mid = lo + (hi - lo) >> 1; // +/-运算符的优先级比移位运算高，所以要加括号 

二分查找适合用有序的顺序表，链表取中点太麻烦，顺序表如果经常插入删除也不合适。

简单有序数组的查找中，直接使用二分法框架进行查找即可，如LeetCode 34.在一个有序数组中找到一个元素的第一次和最后一次出现的位置。要求O(logn)时间复杂度，当然使用二分法。唯一不同的是是要用二分查找两次，第一次出现的位置和最后一次出现的位置。

class Solution_34:
    # 愚蠢的写法
    def _searchRange(self, nums: List[int], target: int) -> List[int]:
        # O(log n) definitely Binary Search
        lo, hi = 0, len(nums) - 1
        res = [-1, -1]
        while lo <= hi:
            mid = (lo + hi) >> 1
            if nums[mid] == target:
                res[0] = mid
                hi = mid - 1
            elif nums[mid] > target:
                hi = mid - 1
            else:
                lo = mid + 1

        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = (lo + hi + 1) >> 1
            if nums[mid] == target:
                res[1] = mid
                lo = mid + 1
            elif nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid - 1

        return res
    
    # fancy一点的写法
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def binsearch(nums, t, eq):
            lo = 0
            hi = len(nums)  # 可以取到最后一个的后面，这样返回值减一指向最后一个
            while lo < hi:
                mid = (lo + hi) >> 1
                if nums[mid] > target or (eq and target == nums[mid]):
                    hi = mid
                else:
                    lo = mid + 1
            return lo

        left = binsearch(nums, target, eq=True)  # 找第一个大于等于target的
        if len(nums) == left or nums[left] != target:
            return [-1, -1]

        return [left, binsearch(nums, target, eq=False) - 1]  # 第二找大于target的

再比如非常非常非常经典的题目LeetCode 4.找两个有序数组的中位数。这个题的关键在于理解中位数是将数组划分为左右两边数目相等的两个子集的数，但是直接用暴力数到中间位置，显然太蠢了。两个数组都是有序的，我们可以使用二分查找来降低复杂度。对于数组A和B，以及他们的长度m和n，我们有i, j将分别将A,B分为两部分，分别是A[:i-1], A[i:m],B[:j-1],A[j:n]。

如果我们能够保证:

len(A[:j-1]) + len(B[:j-1]) == len(A[i:m]) + len(B[j:n]) (or +1)
max(max(A[:j-1]) max(B[:j-1])) < min(min(A[i:m]), min(B[j:n]))

我们就将A+B划分成了等长的（或者长度相差为1的两部分）,我们就找到了中位数。幸运的是A和B是有序的，因此max,min很简单，上述两个条件变成了

i+j == m-i + n-j (or + 1)
B[j-1] <= A[i] and A[i-1] <= B[j]

我们取j = (m + n + 1) // 2 - i，这样我们就能在[0, m]区间上对i进行二分查找，同时使用上面两个限制条件，找到了正确的i之后，我们再对一些特殊的边界条件进行判断处理，就可以得出正确的结果了。

class Solution_4:
    def findMedianSortedArrays(self, A: List[int], B: List[int]) -> float:
        if len(A) > len(B):
            A, B = B, A
        m = len(A)
        n = len(B)
        left, right = 0, m   # 二分查找的区间
        while left <= right:
            i = left + (right - left) // 2
            j = (m + n + 1) // 2 - i
            if i < m and B[j-1] > A[i]:
                left = i + 1
            elif i > 0 and A[i-1] > B[j]: 
                right = i - 1
            else:
                # 一些特殊情况需要单独判断
                if i == 0:        #  A的左半部分为空
                    maxleft = B[j-1]
                elif j == 0:      # B的左半部分为空
                    maxleft = A[i-1]
                else:
                    maxleft =  max(A[i-1], B[j-1])
                
                if (m + n) & 1:        # 奇数个长度，左边比右边多一个，
                    return maxleft     # 取左边最大值

                if i == m:        # A的右半部分为空
                    minright=B[j]
                elif j==n:        # B的右半部分为空
                    minright=A[i]
                else:
                    minright = min(A[i], B[j])
      
                return (maxleft + minright) / 2

然而有一类题目中，并没有一个明确的表要去查找，而是解在一个可能的区间内，或者解可以通过构造的方式映射到一个区间的，在这个区间上就适合使用二分查找。如LeetCode 1201.找出第n个能够被a或b或c整除的正整数，n,a,b,c取值范围为[1,1e9]，解的值不会超过2e9，暴力的办法是对从1开始对正整数依次检查是否满足，数到第n个的时候即为答案，如下暴力解法。但这种效率太低，很多无用的检查。更好的办法是根据a,b,c进行生成，他们的倍数自然是能够被它们整除的数。只需要从最小的开始，生成到第n个即为答案。实际上对于1e9数量级，必须思考O(logn)的解法。

定义：f(k)表示[1, k]能够被a/b/c整除的数的数目。注意对于能被a整除的数有k//a个，则根据容斥原理。可以得到：

def f(k):
    """f(k) return the number of numbers that can be divide by a/b/c"""
    return k // a + k // b + k // c - k // LCM(a, b) - k // LCM(b, c) - k // LCM(a, c) + k // LCM(a, b, c=c)

其中LCM是最小公倍数计算。显然f(k)是一个随k递增的区间，只要找到起始的区间端点，我们就能在这个问题上应用二分查找。显然区间的左端点是min(a, b, c),即n取值为1时，答案为a,b,c中的最小值，右端点最大为n*max(a, b, c)这样我们就可以进行二分查找了，如下二分解法。

class Solution_1201:
    # 暴力解法
    def _TLE_nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        # 这个方法要生成所有的临时结果，如果n的值很大(1e9)则会超时
        tojump = {} # 用于筛选掉重复的情况，a的b倍和b的a倍是重复的。
        for i in [a, b, c, a * b, a * c, b * c]:
            tojump[i] = 1

        res = 0
        ia = ib = ic = 1
        i = 0
        while i < n:
            t = min(a * ia, b * ib, c * ic)
            if t in tojump and tojump[t] == 1:
                tojump[t] = 0
                res = t
                i += 1
            elif t not in tojump:
                res = t
                i += 1
            ia += (t == a * ia)
            ib += (t == b * ib)
            ic += (t == c * ic)
        return res
    # 二分解法
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        def gcd(a, b):
            """计算最大公约数"""
            while b > 0:
                a, b = b, a % b
            return a

        def LCM(a, b, c=1):
            """计算最小公倍数"""
            if c == 1:
                return (a * b) // gcd(a, b)
            lcm_ab = (a * b) // gcd(a, b)
            lcm_bc = (b * c) // gcd(b, c)
            return (lcm_ab * lcm_bc) // gcd(lcm_ab, lcm_bc)

        def f(k):
            """f(k) return the number of numbers that can be divide by a/b/c"""
            return k // a + k // b + k // c - k // LCM(a, b) - k // LCM(b, c) - k // LCM(a, c) + k // LCM(a, b, c=c)

        left = min(a, b, c)
        right = min(n * max(a, b, c), int(2e9 + 1))
        while left < right:
            mid = (right + left) // 2
            if f(mid) < n:
                left = mid + 1
            else:
                right = mid
        return left  # 返回的恰好时第一个能够被a/b/c整除的,且f(k)=n的数

再如LeetCode 410.将一个数组分成m个非空子数组，找到使得子数组和的最大值最小得划分，求这个最小值。显然，对于一个长度为n得数组，有C(n-1, m-1)种划分方式，枚举无法解决这个问题。

可以看到，子数组和得最大值得取值范围为[max(A), sum(A)]，即能够将数组A最大的元素单独划到一个子数组，其他子数组和都比最大元素值小时，max(A)是要求的结果，能够将数组A不进行划分(m=1)时，sum(A)是结果。这是一个升序的区间，可以在这个区间内查找。但我们还少了能检查一个值是否满足条件的方法，要检查的值是一个给定的子数组和的界max_sum。即检查

给定一个max_sum,能否分成m个sum(·)<=max_sum的子集？

直接check好像不太行的通，所以我们要反过来思考。

数组A不大于max_sum子数组的数目，是否超过m个？

显然第二个目标个验证起来更简单，因此解法如下：

class Solution_410:
    def _splitArray(self, nums: List[int], m: int) -> int:
        # 结果的取值区间为： [max(nums), sum(nums)]
        # 可以在这个区间内进行二分查找
        # 给定一个检查的值max_sum, 确定数组能否分成m个 sum<= max_sum的子集
        # 可以反过来检查不大于max_sum的子数组数目，如果超过m个则不能划分
        def can_split(max_sum):
            cur, cuts = 0, 0
            for x in nums:
                if cur + x > max_sum:
                    cuts += 1
                    cur = x
                else:
                    cur += x
            return cuts < m  # (cuts + 1) < m 最后cur中还剩一个子集。

        lo = max(nums)
        hi = sum(nums)
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if can_split(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo

与此类似的还有LeetCode 875.题，思路很相似，就不赘述了。

class Solution_875:
    def minEatingSpeed(self, piles: List[int], H: int) -> int:
        def can(K):
            hours = 0
            for p in piles:
                hours += math.ceil(p / K)
            return hours <= H  # (hours + 1 <= H)

        # 解的取值区间[1, max(pile)] 最少吃一个，最多一次吃一堆
        lo = 1
        hi = max(piles)
        while lo < hi:
            mid = (lo + hi) >> 1
            if can(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo

时间复杂度要求比较高的题目中，可以考虑使用二分查找，前提是：

解在一个有序的数组中/在一个单调的区间内
可以构造出对关键字（可能解）的快速比较（判断）方法

同时二分可以结合其他算法思想，求解问题，经典丢鸡蛋问题LeetCode 887.给定楼层N和鸡蛋数目k,求最少多少步能够找出确定在某一层F丢鸡蛋会碎，在f < F丢鸡蛋不会碎。首先可以使用带记忆的搜索(DP)+二分查找的方式。定义:状态(k, N)，DP(k,N)在该状态解这个问题需要的最多的步数。状态转移：我们在X层丢鸡蛋，

碎了状态变成(K-1, X-1)
没碎状态变成(K, N-X)

则：

\[dp(k, n) = \min_{1<=X<=N} (max(dp(k-1, x-1), dp(k, n-x)))\]

注意到：

t1 = dp(k-1, x-1)随x单调增
t2 = dp(k, n-x)随x单调减

即max(t1,t2)是二者图像的上半部分，因此查找x可以二分进行，同时注意边界条件是t1,t2两者不一定相交于整数X, 因此这时要检查两个。

class Solution_887:
    def superEggDrop(self, K: int, N: int) -> int:
        # DP(memo+search) + binary search
        # 状态(K, N)
        # 如果我们从X层丢鸡蛋，碎了状态变成(K-1, X-1), 没碎状态变成(K, N-X)
        # 定义dp(k, n) = 在状态(k, n)下解这个问题需要的最多的步数，则
        #   dp(k, n) = min_{1<=X<=N} (max(dp(k-1, x-1), dp(k, n-x)))
        # 注意到 t1 = dp(k-1, x-1), 随x单调增
        #        t2 = dp(k, n-x), 随x单调减
        # 于是max(t1,t2)是二者的上半部分, 因此查找x可以二分进行。
        # 边界条件是两者不一定相交于整数X, 因此这时要检查两个。
        # Time: O(KN log N)
        # space: O(KN)
        # https://leetcode.com/articles/super-egg-drop/ Solution1
        dp = {}

        def foo(k, n):
            if (k, n) in dp:
                return dp[(k, n)]

            if n == 0:
                ans = 0
            elif k == 1:
                ans = n
            else:
                lo, hi = 1, n
                while lo + 1 < hi:
                    x = (lo + hi) >> 1
                    t1 = foo(k - 1, x - 1)
                    t2 = foo(k, n - x)

                    if t1 < t2:
                        lo = x
                    elif t1 > t2:
                        hi = x
                    else:
                        lo = hi = x
                ans = 1 + min(max(foo(k - 1, x - 1), foo(k, n - x)) for x in (lo, hi))
            dp[(k, n)] = ans
            return dp[(k, n)]

        return foo(K, N)

反向思考这个问题，假如给出步数T，K个鸡蛋, f(T,K)表示我们能够解原问题的楼层数的最大值。（能够解原问题指：找到0<=F<=f(T,K)即确定找到楼层F)。则问题转换为寻找满足f(T,K) >= N的T的最小值。

在最优策略下，我们在解X'层丢一个鸡蛋，如果破了，我们可以解f(T-1, K-1), 如果没有碎，可以解f(T-1, K)。（这里的解f等价于上面解问题）。于是：

f(T, K) = 1 + f(T-1, K-1) + f(T-1, K)

且显然f(t, 1) = t (t>=1), f(1, k) = 1(k>=1) 接下来用两种方式解的f(t, k)的通项

记:g(t, k) = f(t, k) - F(t, k-1)，又有： f(t, k) = 1 + f(t-1, k-1) + f(t-1, k) f(t, k-1) = 1 + f(t-1, k-2) + f(t-1, k-1)

则:
```
 g(t, k) = f(t, k) - f(t, k-1) 
         = f(t-1, k) - f(t-1, k-2) 
         = g(t-1, k) + g(t-1, k-1)
```
上式子 g(t, k) = g(t-1, k) + g(t-1, k-1)是一个二项分布的递归式，其解为g(t, k) = C(t, k+1) 则：f(t, k) = sum_{1<=x<=K} g(t, x) = sum C(t, x)
另一个角度来看，我们有t次尝试和k个鸡蛋，因此这是一个长度为t,失败（鸡蛋碎）次数最多为k的尝试序列。没有失败的是C(n, 0), 一次失败是C(n, 1)…, 综合起来就是sum C(t, x)

使用C(n, k+1) = C(n, k) * (n-k)/(k+1)可以简化计算。

class Solution_887:
    def superEggDrop(self, K, N):
        def combination(x):
            # C(n, k + 1) = C(n, k) * (n-k)/(k+1)
            ans = 0
            r = 1
            for i in range(1, K+1):
                r *= x - i + 1   # r = r * (x - (i-1)) // ((i-1) + 1)
                r //= i
                ans += r
                if ans >= N:
                    break
            return ans

        lo, hi = 1, N
        while lo < hi:
            mi = (lo + hi) >> 1
            if combination(mi) < N:
                lo = mi + 1
            else:
                hi = mi
        return lo

插值查找

插值查找是二分查找的改进办法，每次计算中间节点时，改用

mid = lo + (key - A[lo]) // (A[hi] - A[lo]) * (hi - lo)

简单但来说就是将二分查找中的1/2换成了与key和A有关的数值，每次取得mid更加接近关键字key。这个算法适合与A中关键字分布均匀的情况。我在实际中从来没用过。

树表查找

树表查找即使用树数结构对应的查找方法，典型的有二叉查找树（实际上二分查找的过程就对应一棵二叉查找树），此外还有为了保证最差性能的平衡二叉查找树，红黑树，以及可以有多个分支的B树和B+树等，查找树也是有序结构，查找时并不需要遍历整个树，这一部分之后单独来写一些。

图查找

在图数据结构上进行查找，需要遍历整个图。主要方法有BFS/DFS。图算法也之后再说。

哈希查找

哈希是用散列表数据结构的查找算法，最好的情况下hash查找时间复杂度为O(1), 同样后面说。

此外还有一些高级数据结构，如线段树，树形数组等可以用于区间查找，如线段树可以在O(logn)时间内找到数组任意区间内的最值。

本次的重点是二分查找，尤其是二分不仅可以用在数组排序，查找上面，还可以对于一个给定区间的解，尝试构造出判断一个可能解是否满足要求的函数，然后就能利用二分在解区间上搜索，降低时间复杂度。

二分查找是一个相当简单的算法，但是要做到简单算法的的灵活运用。还是，多做题，多总结~