# Binary Search

* 二分搜索的经典写法。需要注意的三点：
  1. 循环退出条件，注意是 low <= high，而不是 low < high。
  2. mid 的取值，mid := low + (high-low)>>1
  3. low 和 high 的更新。low = mid + 1，high = mid - 1。

```go
```

* 二分搜索的变种写法。有 4 个基本变种:
  1. 查找第一个与 target 相等的元素，时间复杂度 O(logn)
  2. 查找最后一个与 target 相等的元素，时间复杂度 O(logn)
  3. 查找第一个大于等于 target 的元素，时间复杂度 O(logn)
  4. 查找最后一个小于等于 target 的元素，时间复杂度 O(logn)

```go
// 二分查找第一个与 target 相等的元素，时间复杂度 O(logn)


// 二分查找最后一个与 target 相等的元素，时间复杂度 O(logn)


// 二分查找第一个大于等于 target 的元素，时间复杂度 O(logn)


// 二分查找最后一个小于等于 target 的元素，时间复杂度 O(logn)
```

* 在基本有序的数组中用二分搜索。经典解法可以解，变种写法也可以写，常见的题型，在山峰数组中找山峰，在旋转有序数组中找分界点。第 33 题，第 81 题，第 153 题，第 154 题，第 162 题，第 852 题

```go
```

* max-min 最大值最小化问题。求在最小满足条件的情况下的最大值。第 410 题，第 875 题，第 1011 题，第 1283 题。

|      No.     | Title                                                   | Solution |    Difficulty    |  TimeComplexity | SpaceComplexity |    Favorite   |   Acceptance  |
| :----------: | ------------------------------------------------------- | :------: | :--------------: | :-------------: | :-------------: | :-----------: | :-----------: |
|     0004     | Median of Two Sorted Arrays                             |          |       Hard       |                 |                 |               |     30.8%     |
|     0029     | Divide Two Integers                                     |          |      Medium      |                 |                 |               |     16.6%     |
|     0033     | Search in Rotated Sorted Array                          |          |      Medium      |                 |                 |               |     35.7%     |
|     0034     | Find First and Last Position of Element in Sorted Array |          |      Medium      |                 |                 |               |     37.1%     |
|     0035     | Search Insert Position                                  |          |       Easy       |                 |                 |               |     42.8%     |
|     0050     | Pow(x, n)                                               |          |      Medium      |     O(log n)    |       O(1)      |               |     30.8%     |
|     0069     | Sqrt(x)                                                 |          |       Easy       |     O(log n)    |       O(1)      |               |     34.9%     |
|     0074     | Search a 2D Matrix                                      |          |      Medium      |                 |                 |               |     37.5%     |
|     0081     | Search in Rotated Sorted Array II                       |          |      Medium      |                 |                 |               |     33.5%     |
|     0153     | Find Minimum in Rotated Sorted Array                    |          |      Medium      |                 |                 |               |     46.0%     |
|     0154     | Find Minimum in Rotated Sorted Array II                 |          |       Hard       |                 |                 |               |     41.9%     |
|     0162     | Find Peak Element                                       |          |      Medium      |                 |                 |               |     43.9%     |
|     0167     | Two Sum II - Input array is sorted                      |          |       Easy       |       O(n)      |       O(1)      |               |     55.4%     |
|     0174     | Dungeon Game                                            |          |       Hard       |                 |                 |               |     33.2%     |
|     0209     | Minimum Size Subarray Sum                               |          |      Medium      |       O(n)      |       O(1)      |               |     39.2%     |
|     0222     | Count Complete Tree Nodes                               |          |      Medium      |       O(n)      |       O(1)      |               |     48.9%     |
|     0230     | Kth Smallest Element in a BST                           |          |      Medium      |       O(n)      |       O(1)      |               |     62.2%     |
|     0240     | Search a 2D Matrix II                                   |          |      Medium      |                 |                 |               |     44.2%     |
|     0275     | H-Index II                                              |          |      Medium      |                 |                 |               |     36.2%     |
|     0287     | Find the Duplicate Number                               |          |      Medium      |       O(n)      |       O(1)      |       ❤️      |     57.2%     |
|     0300     | Longest Increasing Subsequence                          |          |      Medium      |    O(n log n)   |       O(n)      |               |     43.7%     |
|     0315     | Count of Smaller Numbers After Self                     |          |       Hard       |                 |                 |               |     42.6%     |
|     0327     | Count of Range Sum                                      |          |       Hard       |                 |                 |               |     35.9%     |
|     0349     | Intersection of Two Arrays                              |          |       Easy       |       O(n)      |       O(n)      |               |     64.5%     |
|     0350     | Intersection of Two Arrays II                           |          |       Easy       |       O(n)      |       O(n)      |               |     51.9%     |
|     0354     | Russian Doll Envelopes                                  |          |       Hard       |                 |                 |               |     36.1%     |
|     0367     | Valid Perfect Square                                    |          |       Easy       |                 |                 |               |     42.0%     |
|     0378     | Kth Smallest Element in a Sorted Matrix                 |          |      Medium      |                 |                 |               |     55.9%     |
|     0392     | Is Subsequence                                          |          |       Easy       |       O(n)      |       O(1)      |               |     49.5%     |
|              | Split Array Largest Sum                                 |          |       Hard       |                 |                 |               |     46.1%     |
|     0436     | Find Right Interval                                     |          |      Medium      |                 |                 |               |     48.4%     |
|     0441     | Arranging Coins                                         |          |       Easy       |                 |                 |               |     42.3%     |
|     0454     | 4Sum II                                                 |          |      Medium      |      O(n^2)     |       O(n)      |               |     54.5%     |
|     0475     | Heaters                                                 |          |      Medium      |                 |                 |               |     33.6%     |
|     0483     | Smallest Good Base                                      |          |       Hard       |                 |                 |               |     36.2%     |
|     0493     | Reverse Pairs                                           |          |       Hard       |                 |                 |               |     26.6%     |
|     0497     | Random Point in Non-overlapping Rectangles              |          |      Medium      |                 |                 |               |     39.1%     |
|     0528     | Random Pick with Weight                                 |          |      Medium      |                 |                 |               |     44.5%     |
|     0658     | Find K Closest Elements                                 |          |      Medium      |                 |                 |               |     41.8%     |
|     0668     | Kth Smallest Number in Multiplication Table             |          |       Hard       |                 |                 |               |     47.7%     |
|     0704     | Binary Search                                           |          |       Easy       |                 |                 |               |     54.0%     |
|     0710     | Random Pick with Blacklist                              |          |       Hard       |       O(n)      |       O(n)      |               |     32.6%     |
|     0718     | Maximum Length of Repeated Subarray                     |          |      Medium      |                 |                 |               |     50.2%     |
|     0719     | Find K-th Smallest Pair Distance                        |          |       Hard       |                 |                 |               |     32.5%     |
|     0744     | Find Smallest Letter Greater Than Target                |          |       Easy       |                 |                 |               |     45.6%     |
|     0778     | Swim in Rising Water                                    |          |       Hard       |                 |                 |               |     54.5%     |
|     0786     | K-th Smallest Prime Fraction                            |          |       Hard       |                 |                 |               |     41.9%     |
|     0793     | Preimage Size of Factorial Zeroes Function              |          |       Hard       |                 |                 |               |     40.7%     |
|     0852     | Peak Index in a Mountain Array                          |          |       Easy       |                 |                 |               |     71.8%     |
|     0862     | Shortest Subarray with Sum at Least K                   |          |       Hard       |                 |                 |               |     25.2%     |
|     0875     | Koko Eating Bananas                                     |          |      Medium      |                 |                 |               |     53.4%     |
|     0878     | Nth Magical Number                                      |          |       Hard       |                 |                 |               |     28.9%     |
|     0887     | Super Egg Drop                                          |          |       Hard       |                 |                 |               |     27.0%     |
|     0911     | Online Election                                         |          |      Medium      |                 |                 |               |     51.2%     |
|     0927     | Three Equal Parts                                       |          |       Hard       |                 |                 |               |     34.5%     |
|     0981     | Time Based Key-Value Store                              |          |      Medium      |                 |                 |               |     54.0%     |
|     1011     | Capacity To Ship Packages Within D Days                 |          |      Medium      |                 |                 |               |     59.6%     |
|     1111     | Maximum Nesting Depth of Two Valid Parentheses Strings  |          |      Medium      |                 |                 |               |     72.5%     |
|     1157     | Online Majority Element In Subarray                     |          |       Hard       |                 |                 |               |     39.6%     |
|     1170     | Compare Strings by Frequency of the Smallest Character  |          |      Medium      |                 |                 |               |     59.5%     |
|     1201     | Ugly Number III                                         |          |      Medium      |                 |                 |               |     26.4%     |
|     1235     | Maximum Profit in Job Scheduling                        |          |       Hard       |                 |                 |               |     47.0%     |
|     1283     | Find the Smallest Divisor Given a Threshold             |          |      Medium      |                 |                 |               |     49.3%     |
|     1300     | Sum of Mutated Array Closest to Target                  |          |      Medium      |                 |                 |               |     43.2%     |
|     1649     | Create Sorted Array through Instructions                |          |       Hard       |                 |                 |               |     36.2%     |
|     1658     | Minimum Operations to Reduce X to Zero                  |          |      Medium      |                 |                 |               |     33.4%     |
| ------------ | ------------------------------------------------------- |  ------- | ---------------- | --------------- |  -------------  | ------------- | ------------- |
