二分(binary search)应用题小结

最近刷了很多二分的应用题，发现有些题目可以直接猜答案，但有些题目是要猜一个对答案有用的variables 然后用它再来计算出答案。发现自己总是不小心就approach错了，所以总结了一番，仔细对比了一下这些题目的wording，整理出来几种类型，每个人的脑回路不同，希望我的思考方式也对大家有帮助，也欢迎补充！

1. 能直接猜答案的

以下的格式是 ： 题目 - 思路 - 题目对return要求的用词

这一类题目，题目都是直接要求你return 某个x，一般用定于 THE x number， return的requirment 就是1纬的。

1608. Special Array With X Elements Greater Than or Equal X (Easy）
        # directly guess x and count the nums >= x

"Return x if the array is ...."

1802. Maximum Value at a Given Index in a Bounded Array (Medium)
        # directly guess the value of the maximum index (not the index!)
        # calculate the sum and see if it meets the maxsum requirement
        # twist: arithmetic sequence sum

"Return nums[index] of the constructed array..."

875. Koko Eating Bananas (Medium)
        # directly guess a speed
        # count hours that need to finish all banans

"Return the minimum integer k such that she can eat all the bananas within h hours."

1231. Divide Chocolate (Hard)
        # directly guess the minimum of maximized sweetness
        # count how many K we can divide

"Find the maximum total sweetness of the piece you can get ..."

410. Split Array Largest Sum (Hard)
        # directly guess the minimum largest sum
        # count how many subarrays there are

"Write an algorithm to minimize the largest sum among these m subarrays."

719. Find K-th Smallest Pair Distance (Hard)
        # directly guess dist m
        # count /check Kth pairs have dist <= m

"return the kth smallest distance among all the pairs"

直接猜答案的变形 1

378. Kth Smallest Element in a Sorted Matrix (Medium)
        # directly guess the possible value of the Kth smallest element
        # check if it is the Kth element

"return the kth smallest element in the matrix."

1102. Path With Maximum Minimum Value (Medium)
        # directly guess the minimum value of the maximized path
        # check if a path exists

"find the maximum score of a path starting at ..."

1631. Path With Minimum Effort (Medium)
        # directly guess the minimum effort
        # check if there's such a path

"Return the minimum effort required..."

直接猜答案的变形 2

774. Minimize Max Distance to Gas Station (Hard)
        # twist: assuming the distance between stations are [d1, d2, d3...] 变形在这里
        # directly guess the smallest cut off distance
        # count how many d values meet the category
        # twist: return a real number

"Return the smallest possible value..."

以上的题目都是直接 return binary search 搜出来的值。

直接猜答案的变形 3

1300. Sum of Mutated Array Closest to Target (Medium)
        # (directly) guess the possible sum
        # then calculate the (closest) sum
        # twist: need to compare the left vs. left - 1
        # because the final value can be larger or smaller, we need abs diff

"return the integer value such that..."

这个题其实本质上也属于直接猜答案，但是我们不能直接return，因我们要找cloest to

2. 不能直接猜答案的

可以直接猜答案的题目基本上都长得一样，但不能直接猜答案的题目就是真的五花八门，以下是一些不完全总结，可以看到以下的题目都不是要求return 单个数字，或者某个特定的数字，而是return，符合条件的某些东西。因此我们一般都需要猜符合条件的某一个东西在哪里，然后用那个东西再去推算答案。

type 1: 用binary search return 出来的数，再稍微做一下简单的算数，便是答案

1648. Sell Diminishing-Valued Colored Balls (Medium)
        # guess the cutoff price - variant of 410
        # then count how many orders with such cut off price
        # return the total value of those orders

"Return the maximum total value that you can attain after selling orders colored balls."

4. Median of Two Sorted Arrays (Hard)

    # Twist: guess the cut off index(length) of arr 1 vs. arr 2
    # then calculate the median

"return the median of the two sorted arrays."

这道题的二分法好难想，难点是在于，很难想到我们可以用二分来找什么。。。题目虽然用了定语 the，但是要找的两个array的中位数，所以我们首先要知道array 1和array2的数值情况，因此问题不是一维的。这里推荐 山景城一姐 的youtube视频讲解！

type 2: 找到第一个符合题目条件的位置/index，然后return 所有符合条件的数量



274/275. H-Index (Medium)
        # guess the cutoff index/position of -------> 在它右边的每个值都 >= 右边的长度 ie. n-index
        # check if this index fits the h-index definition
        # then return the length of the right side

这题我做起来觉得很绕。中文思路是 - 想成 guess 第一个符合条件的value的index/位置，然后就可以return 所有符合条件的数量，也就是h-index。
我是做完274/275之后隔了一段时间做的1608，乍眼看还以为是一样的，细看才发现不同，下面给大家highlight出来，也可以看到为什么1608可以直接猜结果，而274不可以。因为1608是直接找那个x的切割点，而274要的是所有满足x数的数量/sub-array长度。因此我们要先找到x是array的第几个位置，再通过这个求长度。这里推荐残酷群群主的视频 - huifeng youtube channel。

"""
# 1608
a number x such that there are exactly x numbers in nums that are greater than or equal to x. Notice that x does not have to be an element in nums.

# 274
return compute the researcher's h-index.
an index h if h of their n papers have at least h citations each, and the other n − h papers have no more than h citations each.
"""

658. Find K Closest Elements (Medium)
        # guess the left boundary - 所有符合条件的数中，左边第一个
        # check if (target - left boundary) < left boundary + k - target
        # return left boundary + k

"return the k closest integers to x in the array...."

type 3: 用binary search猜数量，然后猜出来的数量 + 题目要求的k，就是我们要的数。

感觉这种就是专门针对这种missing numbers的题目。

1539. Kth Missing Positive Number (Easy)
        # given that we can have k missing numbers, guess the numbers of not missing number before having k missing numbers
        # binary search returns - the length of not missing numbers
        # missing = nums[mid] - nums[0] - mid (mid 代表的就是 没有miss数字的数量）

        # return not missing number + k + starting value = Kth missing number

1060. Missing Element in Sorted Array (Medium)
        # given that we can have k missing numbers, guess the numbers of not missing number before having k missing numbers
        # binary search returns - the length of not missing numbers
        # return not missing number + k + starting value = Kth missing number

这题的思路上跟上题一样，不一样的是上一题的starting value一定是1，这题却可以从任何数值开始


type 4: 主要考点不是binary search，但使用binary search 做起来方便很多

792. Number of Matching Subsequences (Medium)


最后我想跟大家分享的一个心得是，总结套路是为了整理自己的知识体系，方便消化。切记不要看到题，觉得似曾相识，没有认真思考就开始搬套路，那样本末倒置，很容易发现怎么写都不对。自己在写1608的时候就犯了这个错误，没有仔细审题，或者自习思考就想直接套用274的想法，也告诫自己不要再犯了。。。

感谢LZ分享！！！！

感谢总结！