友情支持
如果您觉得这个笔记对您有所帮助,看在D瓜哥码这么多字的辛苦上,请友情支持一下,D瓜哥感激不尽,😜
有些打赏的朋友希望可以加个好友,欢迎关注D 瓜哥的微信公众号,这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi 。因为众所周知的原因,有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
Modified Binary Search 改进的二分搜索
当你需要解决的问题的输入是排好序的数组,链表,或是排好序的矩阵,要求咱们寻找某些特定元素。这个时候的不二选择就是二分搜索。这种模式是一种超级牛的用二分来解决问题的方式。
对于一组满足上升排列的数集来说,这种模式的步骤是这样的:
-
首先,算出左右端点的中点。最简单的方式是这样的: \(middle = (start + end) / 2\)。但这种计算方式有不小的概率会出现整数越界。因此一般都推荐另外这种写法: \(middle = start + (end - start) / 2\).
-
如果要找的目标改好和中点所在的数值相等,我们返回中点的下标就行
-
如果目标不等的话:我们就有两种移动方式了如果目标比中点在的值小(key < arr[middle]):将下一步搜索空间放到左边(end = middle - 1)
-
如果比中点的值大,则继续在右边搜索,丢弃左边:left = middle + 1
经典题目
-
[1150-check-if-a-number-is-majority-element-in-a-sorted-array]
-
[1170-compare-strings-by-frequency-of-the-smallest-character]
-
[1292-maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold]
-
[1439-find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows]
-
[1477-find-two-non-overlapping-sub-arrays-each-with-target-sum]
-
[1498-number-of-subsequences-that-satisfy-the-given-sum-condition]
-
[1521-find-a-value-of-a-mysterious-function-closest-to-target]
-
[1608-special-array-with-x-elements-greater-than-or-equal-x]
-
[1964-find-the-longest-valid-obstacle-course-at-each-position]
-
[2009-minimum-number-of-operations-to-make-array-continuous]
-
[2035-partition-array-into-two-arrays-to-minimize-sum-difference]
-
[2064-minimized-maximum-of-products-distributed-to-any-store]
-
[2137-pour-water-between-buckets-to-make-water-levels-equal]
-
[2529-maximum-count-of-positive-integer-and-negative-integer]
-
[2817-minimum-absolute-difference-between-elements-with-constraint]
-
[3007-maximum-number-that-sum-of-the-prices-is-less-than-or-equal-to-k]
-
[3113-find-the-number-of-subarrays-where-boundary-elements-are-maximum]
-
[3116-kth-smallest-amount-with-single-denomination-combination]
-
[3135-equalize-strings-by-adding-or-removing-characters-at-ends]
-
[3231-minimum-number-of-increasing-subsequence-to-be-removed]
-
[3296-minimum-number-of-seconds-to-make-mountain-height-zero]
-
[3346-maximum-frequency-of-an-element-after-performing-operations-i]
-
[3347-maximum-frequency-of-an-element-after-performing-operations-ii]