LeetCode Summary(1) -- Binary Search

Binary Search  题目

Binary Search 题目相对高频，因为套路固定，必须一次写对，几道题目大同小异。
相比于O(n) 的search，Binary Search O(log(n)) 搞定.

• Search Insert Position
• Search a 2D Matrix
• Search for a Range
• Search in Rotated Sorted Array
• Search in Rotated Sorted Array II
• Median of Two Sorted Array

下面这几道题目用的Binary Search 思想，但不是标准的Binary Search. 

• Divide Two Integers
• Pow(x, n)
• Sqrt(x)

Source Code

 public int search(int[] A, int target) {  
         if (A == null || A.length == 0) {  
             return -1;  
         }  
           
         int start, end, mid;  
         start = 0;  
         end = A.length - 1;  
    
         while (start + 1 < end) {  
             mid = start + (end - start) / 2;  
             if (target == A[mid]) {  
                 return mid;  
             } else if (target < A[mid]) {  
                 end = mid;  
             } else {  
                 start = mid;  
             }  
         }  
    
         if (target == A[start]) {  
             return start;  
         }  
    
         if (target == A[end]) {  
             return end;  
         }  
           
         return -1;  
     }  

• start + 1 < end
• mid = start + (end - start) / 2;
• A[start], A[end] 的判断别漏

每个题目需要关注的是

• target 和 A[mid] 的判断条件，以及对应的动作
• 最后的结果处理，整合

1. Search Insert Position

这题目主要处理corner case. [1,3,5,6], 2 → 1, [1,3,5,6], 7 → 4,[1,3,5,6], 0 → 0

最后在处理结果时候，除了 start, end 还要考虑是不是 target > A[end], target < A[start]. 

其实这5中情况可以和套路中 start，end 判断合并(每次写好代码记得看看能不能简化)

target <= A[start] -->  start;   target > A[end] --> end + 1;   else --> end;

2. Search a 2D Matrix

这题其实跟 search in int[] 一样， start = 0， end = m * n -1; 主要是mid 取值的处理，

element = matrix[mid / n][mid % n]

3. Search for a Range
这题很好，要走两边，先取leftBound，再取rightBound. 

代码上的处理: 

a.取leftBound 时候, target == A[mid] --> end = mid;  像个window 一样左移，这样即便是取到了duplicate的右边，最后一样能取到最左边的那个 target. 

因为一定是end 或者start 的一个，所以 在边界处理的时候会给 bound[0] 赋值，

b. 取rightBound 一样，只是 start = mid; 最后要先判断 target == A[end]. 因为test cast[2, 2] 2.

c. 第一次可能找不到target，记得直接return [-1, -1] 省下第二遍，第二遍如果进行，一定有值

4. Search in Rotated Sorted Array
Binary Search 一定要在Sorted 的部分进行，所以要先判断连续空间

A[start] < A[mid] (start, mid) 连续，判断 target >= A[start] && target < A[mid]

A[mid] < A[end] (mid, end) 连续,  同理

5. Search in Rotated Sorted Array II
与I 不同的是, 多了一种情况 A[mid] = A[start], 但是因为很多case，不能轻易用

A[start] <= A[mid]. 这样保证不了 (start, end) 连续，所以此时，start++, skip 掉useless节点

case [1, 3, 1, 1, 1] 3

6. Median of Two Sorted Array
TODO:
这题O(log(m+n)) 的方法我还没细琢磨明白.



1. Divide Two Integers
限制了操作类型，Can't use *, /, %. Could use +, -, <<,  >>.  正负号不用管，都弄成正得，用变量记录下来正负，结果时候加上就行.  要用long 代替int，防止overflow

用bit 比较方便，用a - b的最大倍数 (b << shift) <= a. 

result += 1 << (shift - 1); a -= (b <<(shift - 1)); 

2. Pow(x, n)
Recursive + Binary Search. 

求Pow(x, n)，先求Pow(x, n/2)，注意n % 2 == 0? 这样递归往下走,  用Binary Search 比每次* x 快的多得多。注意n < 0 以及 n = Integer.MIN_VALUE的case

3. Sqrt(x)
先理解题意，不能整开方的，比如83， sqrt 是 9. 都是int，别傻不拉几以为不能算呢.
从start = 0, end = x / 2 + 1. 来算, 最基本的Binary Search，但是要注意 mid * mid overflow，所以这里都是 mid == x / mid 来比较，即便是不考虑溢出，这样也是有好处的，比如说 83/ 9 == 9,
如果用 *, 不相等.