二分探索

二分探索は、ソート済みの範囲を一歩ごとに半分にして、最後の一つまで絞り込む手法です。難しいのは、問題の中に二分できる単調性が隠れていると気づくことです。Koko Eating Bananas なら最も遅い食べる速さ、Magnetic Force Between Two Balls なら最大の最小間隔を探します。

4 つの章は、ソート済み配列での探索から答えの二分探索、山が一つだけの関数での三分探索へと進み、最後は総合問題です。スライディングウィンドウの次に取り組むのがおすすめですが、答えの二分探索がまだ当てずっぽうに感じる人は、この問題集だけを単独で練習しても構いません。

103 問レーティング 1477–28064 章

書斎を開く

誰かと一緒にこの問題集を進めたいなら、ログインして書斎を開いてみてください。ヒロインが一問ずつ出題してくれます。

一、Binary Search

§1.1 基礎

問題	レーティング
34. Find First AND Last Position of Element in Sorted Array	未評価
35. Search Insert Position	未評価
704. Binary Search	未評価
744. Find Smallest Letter Greater Than Target	未評価
2529. Maximum Count of Positive Integer AND Negative Integer	未評価

§1.2 発展

問題	レーティング
2300. Successful Pairs of Spells AND Potions	1477
1385. Find the Distance Value Between Two Arrays	未評価
2389. Longest Subsequence with Limited Sum	未評価
1170. Compare Strings by Frequency of the Smallest Character	未評価
2080. Range Frequency Queries	1702
3488. Closest Equal Element Queries	未評価
2563. Count the Number of Fair Pairs	1721
2070. Most Beautiful Item for Each Query	1724
1146. Snapshot Array	1771
981. Time Based Key Value Store	未評価
3508. Implement Router	1851
658. Find K Closest Elements	未評価
1818. Minimum Absolute Sum Difference	1934
911. Online Election	2001
1287. Element Appearing More Than 25 in Sorted Array	未評価
2476. Closest Nodes Queries in a Binary Search Tree	1597

二、Binary Search on Answer

§2.1 最小値を求める

問題	レーティング
1283. Find the Smallest Divisor Given a Threshold	1542
2187. Minimum Time to Complete Trips	1641
1011. Capacity to Ship Packages Within D Days	1725
875. Koko Eating Bananas	1766
3296. Minimum Number of Seconds to Make Mountain Height Zero	未評価
3639. Minimum Time to Activate String	1853
475. Heaters	未評価
2594. Minimum Time to Repair Cars	1915
1482. Minimum Number of Days to Make M Bouquets	1946
3048. Earliest Second to Mark Indices I	2263
1870. Minimum Speed to Arrive on Time	1676
3453. Separate Squares I	1735

§2.2 最大値を求める

問題	レーティング
275. H Index II	未評価
2226. Maximum Candies Allocated to K Children	1646
2982. Find Longest Special Substring That Occurs Thrice II	1773
2576. Find the Maximum Number of Marked Indices	1843
1898. Maximum Number of Removable Characters	1913
1802. Maximum Value at a Given Index in a Bounded Array	1929
1642. Furthest Building You Can Reach	1962
2861. Maximum Number of Alloys	1981
3007. Maximum Number That Sum of the Prices Is Less Than OR Equal to K	2258
2141. Maximum Running Time of N Computers	2265
2258. Escape the Spreading Fire	2347
2071. Maximum Number of Tasks You Can Assign	2648

§2.3 間接的な値でBinary Search

問題	レーティング
3143. Maximum Points Inside the Square	1697
1648. Sell Diminishing Valued Colored Balls	2050

§2.4 最大値の最小化

問題	レーティング
410. Split Array Largest Sum	未評価
2064. Minimized Maximum of Products Distributed to Any Store	1886
3613. Minimize Maximum Component Cost	未評価
1760. Minimum Limit of Balls in a Bag	1940
1631. Path with Minimum Effort	1948
2439. Minimize Maximum of Array	1965
2560. House Robber IV	2081
778. Swim in Rising Water	2097
2616. Minimize the Maximum Difference of Pairs	2155
3419. Minimize the Maximum Edge Weight of Graph	2243
2513. Minimize the Maximum of Two Arrays	2302
3733. Minimum Time to Complete All Deliveries	未評価
3399. Smallest Substring with Identical Characters II	2376
3605. Minimum Stability Factor of Array	2410

§2.5 最小値の最大化

問題	レーティング
3281. Maximize Score of Numbers in Ranges	1768
3620. Network Recovery Pathways	1998
2517. Maximum Tastiness of Candy Basket	2021
1552. Magnetic Force Between Two Balls	未評価
3710. Maximum Partition Factor	2135
2812. Find the Safest Path in a Grid	2154
2528. Maximize the Minimum Powered City	2236
3600. Maximize Spanning Tree Stability with Upgrades	2301
3449. Maximize the Minimum Game Score	2748
3464. Maximize the Distance Between Points on a Square	2806

§2.6 K 番目に小さい / 大きい値

問題	レーティング
668. Kth Smallest Number in Multiplication Table	未評価
378. Kth Smallest Element in a Sorted Matrix	未評価
719. Find K Th Smallest Pair Distance	未評価
878. Nth Magical Number	1897
1201. Ugly Number III	2039
793. Preimage Size of Factorial Zeroes Function	2100
373. Find K Pairs with Smallest Sums	未評価
1439. Find the Kth Smallest Sum of a Matrix with Sorted Rows	2134
786. K Th Smallest Prime Fraction	2169
3116. Kth Smallest Amount with Single Denomination Combination	2387
3134. Find the Median of the Uniqueness Array	2451
2040. Kth Smallest Product of Two Sorted Arrays	2518
2386. Find the K Sum of an Array	2648
1508. Range Sum of Sorted Subarray Sums	未評価
3691. Maximum Total Subarray Value II	未評価

三、Ternary Search

問題	レーティング
1515. Best Position for a Service Centre	2157

四、その他

問題	レーティング
69. Sqrtx	未評価
74. Search a 2D Matrix	未評価
278. First Bad Version	未評価
374. Guess Number Higher OR Lower	未評価
162. Find Peak Element	未評価
1901. Find a Peak Element II	未評価
852. Peak Index in a Mountain Array	未評価
1095. Find in Mountain Array	1827
153. Find Minimum in Rotated Sorted Array	未評価
154. Find Minimum in Rotated Sorted Array II	未評価
33. Search in Rotated Sorted Array	未評価
81. Search in Rotated Sorted Array II	未評価
222. Count Complete Tree Nodes	未評価
1539. Kth Missing Positive Number	未評価
540. Single Element in a Sorted Array	未評価
4. Median of Two Sorted Arrays	未評価

ルートでは「スライディングウィンドウと Two Pointers」の次に置かれていますが、順番はロックされておらず、ヒロインは変わらずまだ解いていない問題を一問ずつ出してくれます。

レーティングは zerotrac さんによる LeetCode コンテストレーティングです。zerotrac のレーティングがない問題は「未評価」と表示されます。

書斎を開く