Leetcode - Binary Search解法

Binary Search (T(n) = T(n/2) + O(1). =>O(lgN))
适用于sorted array,mid = start + (end-start)/2; //!!!avoid limit error big integer

EX:
Two sum- sorted array
https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
O(nlgn).
外面for loop h或者 low,high
里面start,mid,end 根据index搜

for(int k=0;k<nums.length-1;k++){
            int start=k+1,end=nums.length-1, gap=target-nums[k];
            while(start<=end){//是个范围
                        mid = start + (end-start)/2; //!!!avoid limit error
                        start = mid+1, end = mid-1;

278. Find first bad version F家
--返回是start： end 会落在 non bad的最后一个里面,下一个start落在第一个bad的位置
https://leetcode.com/problems/first-bad-version/

public int firstBadVersion(int n) {
        int start = 1, end = n;
        while(start <= end){
            int mid = start + (end - start)/2;
            if(isBadVersion(mid)){
                end = mid - 1;
            }else{
                start = mid + 1;
            }
        }
        return start;
    }

 Search for range
 https://leetcode.com/submissions/detail/86564241/
--Another approach : find first appearance vs find last appearance(return mid)

if(nums[mid] >= target){//first appearance
            end = mid - 1;
        }

  if(nums[mid] <= target){//last appearance
            start = mid + 1;
        } 

https://leetcode.com/problems/search-for-a-range/

Search insert position
https://leetcode.com/problems/search-insert-position/
 --有时候 return start (low)
» 33. Search in Rotated Sorted Array
http://rainykat.blogspot.com/2017/02/leetcode-33-search-in-rotated-sorted.html 
» 69.367. sqrt(x) F家 /valid perfect square LinkedIn
根据 mid= (left+right)/2来和x/mid比较
http://rainykat.blogspot.com/2016/12/leetcode-sqrtx.html