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 的几个判断条件
  1. 面试官是否要求了不使用 Recursion （如果你不确定，就向面试官询问）
  2. 不用 Recursion 是否会造成实现变得很复杂
  3. Recursion 的深度是否会很深
  4. 题目的考点是 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/