ZXAlgorithm - C2 Binary Search
Binary search template: 复杂度，递归与非递归，二分的痛点，模板
OOXX: Find first/last value meeting some condition
找到满足某个条件的第一个位置或者最后一个位置
Half half: Remain the half containing solution
保留有解的一半，或者去掉无解的一半
1 二分法模板
复杂度
Recursion or Non-recursion
- 面试中是否使用 Recursion 的几个判断条件
- 面试官是否要求了不使用 Recursion （如果你不确定，就向面试官询问）
- 不用 Recursion 是否会造成实现变得很复杂
- Recursion 的深度是否会很深
- 题目的考点是 Recursion vs Non-Recursion 还是就是考你是否会Recursion？
- 记住：不要自己下判断，要跟面试官讨论！
痛点
死循环，循环结束条件，指针变化
模板Template
- S
Public start, end;
Private mid; - D
Start + 1 < end 相邻退出
Start + (end-start)/2
A[mid] ==,<,> - E
A[start][end]? Target
一句话概括：相邻就退出
例题
LeetCode 704.Binary search
https://leetcode.com/problems/binary-search/
https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/submissions/1
2 OOXX
一般会给你一个数组，让你找数组中第一个/最后一个满足某个条件的位置
例题
LeetCode 278.First bad version
https://leetcode.com/problems/first-bad-version/description/
D: isBadVersion，通过等于来解决第一个还是最后一个的问题
Lintcode Search in a big sorted array
https://blog.csdn.net/willshine19/article/details/49094139
https://www.jiuzhang.com/solutions/search-in-a-big-sorted-array/
D: Big matrix use *2 to find the upper bound, index = 1; index = index * 2
LeetCode 153.Find minimum in rotated sorted array
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/
https://www.jiuzhang.com/solution/find-minimum-in-rotated-sorted-array/
D: Find first position <= or < last number; Consider 2 situations to select end to be target
E: ? Nums[first] <= target
- Related practice:
LeetCode 74.Search a 2D matrix
https://leetcode.com/problems/search-a-2d-matrix/description/
https://www.jiuzhang.com/solution/search-a-2d-matrix/
LeetCode 240.Search a 2D matrix 2
https://leetcode.com/problems/search-a-2d-matrix-ii/description/
https://www.jiuzhang.com/solution/search-a-2d-matrix-ii/
Smallest rectangle enclosing black pixels
https://www.lintcode.com/problem/smallest-rectangle-enclosing-black-pixels/description
https://www.jiuzhang.com/solution/smallest-rectangle-enclosing-black-pixels/
69. Sqrt(x)
https://leetcode.com/problems/sqrtx/
https://leetcode.com/problems/sqrtx/discuss/25061/Python-binary-search-solution-(O(lgn)).
3 Half half
保留有解的一半
Maximum number in mountain sequence
D: nums[mid] > nums[mid + 1], 因为相邻就退出，mid肯定不是start 也不是end
E: Math.max(nums[start], nums[end])
LeetCode 162.Find peak element
https://leetcode.com/problems/find-peak-element/description/
https://www.jiuzhang.com/solution/find-peak-element/
D: nums[mid] nums[mid - 1] nums[mid + 1],之间的关系，有四种情况
E: Math.max(nums[start], nums[end])
LeetCode 33.Search in rotated sorted array
https://leetcode.com/problems/search-in-rotated-sorted-array/description/
https://www.jiuzhang.com/solution/search-in-rotated-sorted-array/
D: nums[start] nums[mid] divide into red line or green line casue start < mid target 在A[start]和A[end]之间
E: ?nums[start] or nums[end] == target
LeetCode 189.Rotate Array
https://leetcode.com/problems/rotate-array/description/
https://www.jiuzhang.com/solution/rotate-array/
** 410. Split Array Largest Sum**
https://leetcode.com/problems/split-array-largest-sum/
