Binary Search

• 二分搜索的经典写法。需要注意的三点：

  1. 循环退出条件，注意是 low <= high，而不是 low < high。

  2. mid 的取值，mid := low + (high-low)>>1

  3. low 和 high 的更新。low = mid + 1，high = mid - 1。

• 二分搜索的变种写法。有 4 个基本变种:

  1. 查找第一个与 target 相等的元素，时间复杂度 O(logn)

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

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

  4. 查找最后一个小于等于 target 的元素，时间复杂度 O(logn)

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


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


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


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

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

• 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%
------------	-------------------------------------------------------	-------	----------------	---------------	-------------	-------------	-------------