# 17 Binary Search

**2分模板：**

[L458 Last Position of Target](17-binary-search/l458-last-position-of-target)

[L14 First Position of Target](17-binary-search/l14-first-position-of-target)

[L462 Total Occurrence of Target](17-binary-search/l462-total-occurrence-of-target)

**普通2分：**

[74 Search in a 2D Matrix](17-binary-search/74-search-in-a-2d-matrix) (L28)

[240 Search in a 2D matrix II](17-binary-search/240-search-in-a-2d-matrix-ii) (L38)

[162 Find Peak Element](17-binary-search/162-find-peak-element) (L75)

[L390 Find Peak Element II](17-binary-search/l390-find-peak-element-ii)

[L585 maximum Number in Mountain Sequence](17-binary-search/l585-maximum-number-in-mountain-sequence)

[278 First Bad Version (L74)](17-binary-search/l74-first-bad-version)

[35 Search Insert Position](17-binary-search/35-search-insert-position) (L60)

[L447 Search in a Big Sorted Array](17-binary-search/l447-search-in-a-big-sorted-array) (702)

[L459 Closest Number in Sorted Array](17-binary-search/l459-closest-number-in-sorted-array)

[L460 K closest Numbers in Sorted Array](17-binary-search/l460-k-closest-numbers-in-sorted-array)

[744 Find Smallest Letter Greater Than Target](17-binary-search/744-find-smallest-letter-greater-than-target)

[1064 Fixed Point](17-binary-search/1064-fixed-point)

[1228 Missing Number In Arithmetic Progression](math/1228-missing-number-in-arithmetic-progression)

[528 Random Pick with Weight](max-subarrays/528-random-pick-with-weight)&#x20;

[L194 Find Words](17-binary-search/l194-find-words)

**复杂一点的2分搜索：**

[Rotate Arrays](rotated-arrays)

[540 Single Element in a Sorted Array](17-binary-search/540-single-element-in-a-sorted-array)

[34 Search for a Range](17-binary-search/24-search-for-a-range) (L61)

[302 Smallest Rectangle Enclosing Black Pixels](17-binary-search/302-smallest-rectangle-enclosing-black-pixels) - 还可以用bfs，不过2分比较好 (L600)

[275 H-Index II](17-binary-search/275-h-index-ii) -- 九章模板套不了，二分终极版

[L824 Single Number IV](31-bit-manipulation/l824-single-number-iv)

[1539 Kth Missing Positive Number](17-binary-search/1539-kth-missing-positive-number) -- 九章模板套不了，好像那些答案不在中间的都挺难套九章二分的

[1712 Ways to Split Array Into Three Subarrays](17-binary-search/1712-ways-to-split-array-into-three-subarrays)

**二分答案：**&#x8FD9;种题的 T：O(nlog(answer range))，只能用于答案range是连续而且有一个分界点。写法：一个用来筛选答案的2分函数，在主函数里调用这个函数2分地找。

[287 Find the Duplicate number](17-binary-search/287-find-the-duplicate-number) -- 竟然还能用[142 Linked List Cycle II](18-linkedlist/142-linked-list-cycle-ii)的解法

[367 Valid Perfect Square](17-binary-search/367-valid-perfect-square)

[374 Guess Number Higher or Lower](17-binary-search/374-guess-number-higher-or-lower)

[L437 copy books I](17-binary-search/l437-copy-books-i) - can also use DP

[L438 copy books II](17-binary-search/l438-copy-books-ii) - can also use DP

[410 Split Array Largest Sum](17-binary-search/410-split-array-largest-sum) - can also use DP

pramp mock test 2，grant cut

[L141 Sqrt(x)](17-binary-search/l141-sqrt-x) (69)

[RootOfNumber](17-binary-search/rootofnumber) -- pramp，进化版的[L586 Sqrt(x) II](math/l586-sqrt-x-ii)

[L183 Wood Cut](17-binary-search/l183-wood-cut)

[L254 Drop Egg](17-binary-search/l254-drop-egg) - ctci 6.8

L617 maximum Average Subarray

[881 Boats to Save People](17-binary-search/881-boats-to-save-people)

[1631 Path With Minimum Effort](graph/1631-path-with-minimum-effort)

[441 Arranging Coins](17-binary-search/441-arranging-coins)

[875 Koko Eating Bananas](17-binary-search/875-koko-eating-bananas)

[878 Nth Magical Number](17-binary-search/878-nth-magical-number)

**与树相关的2分：**

[222 Count Complete Tree Nodes](26-tree/222-count-complete-tree-nodes)

[230 Kth Smallest Element in a BST](26-tree/230-kth-smallest-element-in-a-bst)

[270 Closest Binary Search Tree Value](26-tree/270-closest-binary-search-tree-value) - pramp 3 - TreeSet flooring / celing / lower / higher

**Other related:**

375 Guess Number Higher or Lower II - DP or MiniMax

[L586 Sqrt(x) II](math/l586-sqrt-x-ii) --- 牛顿法

L584 Drop Eggs II -- DP

**感觉比较难的二分？：**

[4 Median of Two Sorted Arrays](other/4-median-of-two-sorted-arrays) - 与[230](26-tree/230-kth-smallest-element-in-a-bst)有点像
