友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

微信

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。
modified binary search

当你需要解决的问题的输入是排好序的数组，链表，或是排好序的矩阵，要求咱们寻找某些特定元素。这个时候的不二选择就是二分搜索。这种模式是一种超级牛的用二分来解决问题的方式。

对于一组满足上升排列的数集来说，这种模式的步骤是这样的：

  1. 首先，算出左右端点的中点。最简单的方式是这样的： \(middle = (start + end) / 2\)。但这种计算方式有不小的概率会出现整数越界。因此一般都推荐另外这种写法： \(middle = start + (end - start) / 2\).

  2. 如果要找的目标改好和中点所在的数值相等，我们返回中点的下标就行

  3. 如果目标不等的话：我们就有两种移动方式了如果目标比中点在的值小（key < arr[middle]）：将下一步搜索空间放到左边（end = middle - 1）

  4. 如果比中点的值大，则继续在右边搜索，丢弃左边：left = middle + 1

看到最大化最小值或者最小化最大值就要想到二分答案，这是一个固定的套路。

疑问点

  1. 二分搜索怎样可以确定地取左右端点？

  2. 在 35. 搜索插入位置 - 二分查找总是写不对？一个视频讲透！ 中，作者说“在找到 target 就立刻返回”，这种写法适用范围很窄，多思考体会一下。

经典题目

  1. 4. 寻找两个正序数组的中位数

  2. 33. 搜索旋转排序数组

  3. 34. 在排序数组中查找元素的第一个和最后一个位置

  4. 35. 搜索插入位置

  5. 69. x 的平方根

  6. 74. 搜索二维矩阵

  7. 81. 搜索旋转排序数组 II

  8. 153. 寻找旋转排序数组中的最小值

  9. 154. Find Minimum in Rotated Sorted Array II

  10. 162. Find Peak Element

  11. 167. 两数之和 II - 输入有序数组

  12. 209. 长度最小的子数组

  13. 222. Count Complete Tree Nodes

  14. 240. 搜索二维矩阵 II

  15. [0259-3sum-smaller]

  16. 268. Missing Number

  17. [0270-closest-binary-search-tree-value]

  18. 275. H 指数 II

  19. 278. First Bad Version

  20. 287. 寻找重复数

  21. 300. 最长递增子序列

  22. [0302-smallest-rectangle-enclosing-black-pixels]

  23. [0315-count-of-smaller-numbers-after-self]

  24. [0327-count-of-range-sum]

  25. 349. 两个数组的交集

  26. 350. 两个数组的交集 II

  27. [0352-data-stream-as-disjoint-intervals]

  28. [0354-russian-doll-envelopes]

  29. [0362-design-hit-counter]

  30. [0363-max-sum-of-rectangle-no-larger-than-k]

  31. 367. 有效的完全平方数

  32. 374. 猜数字大小

  33. 378. 有序矩阵中第 K 小的元素

  34. 400. Nth Digit

  35. [0410-split-array-largest-sum]

  36. 436. 寻找右区间

  37. 441. 排列硬币

  38. 456. 132 模式

  39. 475. 供暖器

  40. [0483-smallest-good-base]

  41. [0493-reverse-pairs]

  42. [0497-random-point-in-non-overlapping-rectangles]

  43. 528. Random Pick with Weight

  44. [0532-k-diff-pairs-in-an-array]

  45. [0540-single-element-in-a-sorted-array]

  46. [0611-valid-triangle-number]

  47. [0633-sum-of-square-numbers]

  48. [0644-maximum-average-subarray-ii]

  49. [0658-find-k-closest-elements]

  50. [0668-kth-smallest-number-in-multiplication-table]

  51. [0702-search-in-a-sorted-array-of-unknown-size]

  52. 704. Binary Search

  53. 710. Random Pick with Blacklist

  54. 713. Subarray Product Less Than K

  55. 718. 最长重复子数组

  56. [0719-find-k-th-smallest-pair-distance]

  57. [0729-my-calendar-i]

  58. [0731-my-calendar-ii]

  59. [0732-my-calendar-iii]

  60. 744. Find Smallest Letter Greater Than Target

  61. [0754-reach-a-number]

  62. [0774-minimize-max-distance-to-gas-station]

  63. [0778-swim-in-rising-water]

  64. [0786-k-th-smallest-prime-fraction]

  65. [0792-number-of-matching-subsequences]

  66. [0793-preimage-size-of-factorial-zeroes-function]

  67. [0825-friends-of-appropriate-ages]

  68. [0826-most-profit-assigning-work]

  69. [0852-peak-index-in-a-mountain-array]

  70. [0862-shortest-subarray-with-sum-at-least-k]

  71. 875. Koko Eating Bananas

  72. [0878-nth-magical-number]

  73. [0887-super-egg-drop]

  74. [0888-fair-candy-swap]

  75. [0902-numbers-at-most-n-given-digit-set]

  76. [0911-online-election]

  77. [0981-time-based-key-value-store]

  78. [1004-max-consecutive-ones-iii]

  79. 1011. Capacity To Ship Packages Within D Days

  80. [1027-longest-arithmetic-subsequence]

  81. [1044-longest-duplicate-substring]

  82. [1055-shortest-way-to-form-string]

  83. [1060-missing-element-in-sorted-array]

  84. [1062-longest-repeating-substring]

  85. [1064-fixed-point]

  86. [1095-find-in-mountain-array]

  87. [1099-two-sum-less-than-k]

  88. [1102-path-with-maximum-minimum-value]

  89. [1146-snapshot-array]

  90. [1150-check-if-a-number-is-majority-element-in-a-sorted-array]

  91. [1157-online-majority-element-in-subarray]

  92. [1170-compare-strings-by-frequency-of-the-smallest-character]

  93. [1182-shortest-distance-to-target-color]

  94. [1187-make-array-strictly-increasing]

  95. [1198-find-smallest-common-element-in-all-rows]

  96. [1201-ugly-number-iii]

  97. [1208-get-equal-substrings-within-budget]

  98. [1213-intersection-of-three-sorted-arrays]

  99. [1214-two-sum-bsts]

  100. [1231-divide-chocolate]

  101. [1235-maximum-profit-in-job-scheduling]

  102. [1237-find-positive-integer-solution-for-a-given-equation]

  103. [1268-search-suggestions-system]

  104. [1283-find-the-smallest-divisor-given-a-threshold]

  105. [1292-maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold]

  106. [1300-sum-of-mutated-array-closest-to-target]

  107. [1337-the-k-weakest-rows-in-a-matrix]

  108. [1346-check-if-n-and-its-double-exist]

  109. [1348-tweet-counts-per-frequency]

  110. [1351-count-negative-numbers-in-a-sorted-matrix]

  111. [1385-find-the-distance-value-between-two-arrays]

  112. [1428-leftmost-column-with-at-least-a-one]

  113. [1439-find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows]

  114. [1477-find-two-non-overlapping-sub-arrays-each-with-target-sum]

  115. [1482-minimum-number-of-days-to-make-m-bouquets]

  116. [1483-kth-ancestor-of-a-tree-node]

  117. [1488-avoid-flood-in-the-city]

  118. [1498-number-of-subsequences-that-satisfy-the-given-sum-condition]

  119. [1508-range-sum-of-sorted-subarray-sums]

  120. [1521-find-a-value-of-a-mysterious-function-closest-to-target]

  121. [1533-find-the-index-of-the-large-integer]

  122. [1539-kth-missing-positive-number]

  123. [1552-magnetic-force-between-two-balls]

  124. [1562-find-latest-group-of-size-m]

  125. [1574-shortest-subarray-to-be-removed-to-make-array-sorted]

  126. [1608-special-array-with-x-elements-greater-than-or-equal-x]

  127. [1618-maximum-font-to-fit-a-sentence-in-a-screen]

  128. [1631-path-with-minimum-effort]

  129. [1648-sell-diminishing-valued-colored-balls]

  130. [1649-create-sorted-array-through-instructions]

  131. [1658-minimum-operations-to-reduce-x-to-zero]

  132. [1671-minimum-number-of-removals-to-make-mountain-array]

  133. [1712-ways-to-split-array-into-three-subarrays]

  134. [1713-minimum-operations-to-make-a-subsequence]

  135. [1739-building-boxes]

  136. [1751-maximum-number-of-events-that-can-be-attended-ii]

  137. [1760-minimum-limit-of-balls-in-a-bag]

  138. [1782-count-pairs-of-nodes]

  139. [1793-maximum-score-of-a-good-subarray]

  140. [1802-maximum-value-at-a-given-index-in-a-bounded-array]

  141. [1818-minimum-absolute-sum-difference]

  142. [1838-frequency-of-the-most-frequent-element]

  143. [1847-closest-room]

  144. [1851-minimum-interval-to-include-each-query]

  145. [1855-maximum-distance-between-a-pair-of-values]

  146. [1862-sum-of-floored-pairs]

  147. [1870-minimum-speed-to-arrive-on-time]

  148. [1885-count-pairs-in-two-arrays]

  149. [1889-minimum-space-wasted-from-packaging]

  150. [1891-cutting-ribbons]

  151. [1894-find-the-student-that-will-replace-the-chalk]

  152. [1898-maximum-number-of-removable-characters]

  153. [1901-find-a-peak-element-ii]

  154. [1918-kth-smallest-subarray-sum]

  155. [1923-longest-common-subpath]

  156. [1932-merge-bsts-to-create-single-bst]

  157. [1954-minimum-garden-perimeter-to-collect-enough-apples]

  158. [1956-minimum-time-for-k-virus-variants-to-spread]

  159. [1964-find-the-longest-valid-obstacle-course-at-each-position]

  160. [1966-binary-searchable-numbers-in-an-unsorted-array]

  161. [1970-last-day-where-you-can-still-cross]

  162. [2008-maximum-earnings-from-taxi]

  163. [2009-minimum-number-of-operations-to-make-array-continuous]

  164. [2024-maximize-the-confusion-of-an-exam]

  165. [2031-count-subarrays-with-more-ones-than-zeros]

  166. [2035-partition-array-into-two-arrays-to-minimize-sum-difference]

  167. [2040-kth-smallest-product-of-two-sorted-arrays]

  168. [2054-two-best-non-overlapping-events]

  169. [2055-plates-between-candles]

  170. [2064-minimized-maximum-of-products-distributed-to-any-store]

  171. [2070-most-beautiful-item-for-each-query]

  172. [2071-maximum-number-of-tasks-you-can-assign]

  173. [2080-range-frequency-queries]

  174. [2089-find-target-indices-after-sorting-array]

  175. [2106-maximum-fruits-harvested-after-at-most-k-steps]

  176. [2111-minimum-operations-to-make-the-array-k-increasing]

  177. [2137-pour-water-between-buckets-to-make-water-levels-equal]

  178. [2141-maximum-running-time-of-n-computers]

  179. [2179-count-good-triplets-in-an-array]

  180. [2187-minimum-time-to-complete-trips]

  181. [2223-sum-of-scores-of-built-strings]

  182. [2226-maximum-candies-allocated-to-k-children]

  183. [2234-maximum-total-beauty-of-the-gardens]

  184. [2250-count-number-of-rectangles-containing-each-point]

  185. [2251-number-of-flowers-in-full-bloom]

  186. [2258-escape-the-spreading-fire]

  187. [2271-maximum-white-tiles-covered-by-a-carpet]

  188. [2286-booking-concert-tickets-in-groups]

  189. [2300-successful-pairs-of-spells-and-potions]

  190. [2302-count-subarrays-with-score-less-than-k]

  191. [2332-the-latest-time-to-catch-a-bus]

  192. [2333-minimum-sum-of-squared-difference]

  193. [2354-number-of-excellent-pairs]

  194. [2358-maximum-number-of-groups-entering-a-competition]

  195. [2387-median-of-a-row-wise-sorted-matrix]

  196. [2389-longest-subsequence-with-limited-sum]

  197. [2398-maximum-number-of-robots-within-budget]

  198. [2411-smallest-subarrays-with-maximum-bitwise-or]

  199. [2424-longest-uploaded-prefix]

  200. [2426-number-of-pairs-satisfying-inequality]

  201. [2439-minimize-maximum-of-array]

  202. [2448-minimum-cost-to-make-array-equal]

  203. [2454-next-greater-element-iv]

  204. [2468-split-message-based-on-limit]

  205. [2476-closest-nodes-queries-in-a-binary-search-tree]

  206. [2498-frog-jump-ii]

  207. [2501-longest-square-streak-in-an-array]

  208. [2513-minimize-the-maximum-of-two-arrays]

  209. [2517-maximum-tastiness-of-candy-basket]

  210. [2519-count-the-number-of-k-big-indices]

  211. [2528-maximize-the-minimum-powered-city]

  212. [2529-maximum-count-of-positive-integer-and-negative-integer]

  213. [2540-minimum-common-value]

  214. [2554-maximum-number-of-integers-to-choose-from-a-range-i]

  215. [2555-maximize-win-from-two-segments]

  216. [2557-maximum-number-of-integers-to-choose-from-a-range-ii]

  217. 2560. 打家劫舍 IV — 这道题对二分查找的使用场景又做了拓宽：不仅仅可以使用已经排序的数组，同样可以适用隐含排序的数组。

  218. [2563-count-the-number-of-fair-pairs]

  219. [2565-subsequence-with-the-minimum-score]

  220. [2576-find-the-maximum-number-of-marked-indices]

  221. [2589-minimum-time-to-complete-all-tasks]

  222. [2594-minimum-time-to-repair-cars]

  223. [2601-prime-subtraction-operation]

  224. [2602-minimum-operations-to-make-all-array-elements-equal]

  225. [2604-minimum-time-to-eat-all-grains]

  226. [2616-minimize-the-maximum-difference-of-pairs]

  227. [2659-make-array-empty]

  228. [2702-minimum-operations-to-make-numbers-non-positive]

  229. [2713-maximum-strictly-increasing-cells-in-a-matrix]

  230. [2736-maximum-sum-queries]

  231. [2779-maximum-beauty-of-an-array-after-applying-operation]

  232. [2790-maximum-number-of-groups-with-increasing-length]

  233. [2812-find-the-safest-path-in-a-grid]

  234. [2817-minimum-absolute-difference-between-elements-with-constraint]

  235. [2819-minimum-relative-loss-after-buying-chocolates]

  236. [2824-count-pairs-whose-sum-is-less-than-target]

  237. [2826-sorting-three-groups]

  238. [2830-maximize-the-profit-as-the-salesman]

  239. [2831-find-the-longest-equal-subarray]

  240. [2838-maximum-coins-heroes-can-collect]

  241. [2856-minimum-array-length-after-pair-removals]

  242. [2861-maximum-number-of-alloys]

  243. [2926-maximum-balanced-subsequence-sum]

  244. [2936-number-of-equal-numbers-blocks]

  245. [2940-find-building-where-alice-and-bob-can-meet]

  246. [2941-maximum-gcd-sum-of-a-subarray]

  247. [2945-find-maximum-non-decreasing-array-length]

  248. [2967-minimum-cost-to-make-array-equalindromic]

  249. [2968-apply-operations-to-maximize-frequency-score]

  250. [2970-count-the-number-of-incremovable-subarrays-i]

  251. [2972-count-the-number-of-incremovable-subarrays-ii]

  252. [2981-find-longest-special-substring-that-occurs-thrice-i]

  253. [2982-find-longest-special-substring-that-occurs-thrice-ii]

  254. [3006-find-beautiful-indices-in-the-given-array-i]

  255. [3007-maximum-number-that-sum-of-the-prices-is-less-than-or-equal-to-k]

  256. [3008-find-beautiful-indices-in-the-given-array-ii]

  257. [3048-earliest-second-to-mark-indices-i]

  258. [3049-earliest-second-to-mark-indices-ii]

  259. [3104-find-longest-self-contained-substring]

  260. [3109-find-the-index-of-permutation]

  261. [3113-find-the-number-of-subarrays-where-boundary-elements-are-maximum]

  262. [3116-kth-smallest-amount-with-single-denomination-combination]

  263. [3117-minimum-sum-of-values-by-dividing-array]

  264. [3134-find-the-median-of-the-uniqueness-array]

  265. [3135-equalize-strings-by-adding-or-removing-characters-at-ends]

  266. [3143-maximum-points-inside-the-square]

  267. [3145-find-products-of-elements-of-big-array]

  268. [3152-special-array-ii]

  269. [3155-maximum-number-of-upgradable-servers]

  270. [3161-block-placement-queries]

  271. [3171-find-subarray-with-bitwise-or-closest-to-k]

  272. [3186-maximum-total-damage-with-spell-casting]

  273. [3209-number-of-subarrays-with-and-value-of-k]

  274. [3231-minimum-number-of-increasing-subsequence-to-be-removed]

  275. [3261-count-substrings-that-satisfy-k-constraint-ii]

  276. [3281-maximize-score-of-numbers-in-ranges]

  277. [3288-length-of-the-longest-increasing-path]

  278. [3291-minimum-number-of-valid-strings-to-form-target-i]

  279. [3292-minimum-number-of-valid-strings-to-form-target-ii]

  280. [3296-minimum-number-of-seconds-to-make-mountain-height-zero]

  281. [3312-sorted-gcd-pair-queries]

  282. [3323-minimize-connected-groups-by-inserting-interval]

  283. [3344-maximum-sized-array]

  284. [3346-maximum-frequency-of-an-element-after-performing-operations-i]

  285. [3347-maximum-frequency-of-an-element-after-performing-operations-ii]

  286. [3350-adjacent-increasing-subarrays-detection-ii]

  287. [3356-zero-array-transformation-ii]

  288. [3357-minimize-the-maximum-adjacent-element-difference]

  289. [3369-design-an-array-statistics-tracker]

  290. [3398-smallest-substring-with-identical-characters-i]

  291. [3399-smallest-substring-with-identical-characters-ii]

  292. [3413-maximum-coins-from-k-consecutive-bags]

  293. [3414-maximum-score-of-non-overlapping-intervals]

  294. [3419-minimize-the-maximum-edge-weight-of-graph]

  295. [3449-maximize-the-minimum-game-score]

  296. [3453-separate-squares-i]

  297. [3454-separate-squares-ii]

  298. [3455-shortest-matching-substring]

  299. [3464-maximize-the-distance-between-points-on-a-square]

  300. [3477-fruits-into-baskets-ii]

  301. [3479-fruits-into-baskets-iii]

  302. [3488-closest-equal-element-queries]

  303. [3501-maximize-active-section-with-trade-ii]

参考资料

  1. 704. 二分查找 - 二分查找细节详解，顺便赋诗一首

  2. 153. 寻找旋转排序数组中的最小值 - 一文带你搞定二分查找及多个变种

← Previous: Recursion 递归 | ↑ Up: LeetCode 解题笔记 | Next: Difference Array 差分数组 →