一、二分查找法模板

模板一

public binarySearch() {
    while(left < right) {
        mid = (right - left) >>> 1;
        if(check(mid)) {
            left = mid + 1;
        }else {
            right = mid;
        }
    }
}

模板二

public binarySearch() {
    while(left < right) {
        mid = (right - left + 1) >>> 1;
        if(check(mid)) {
            right = mid - 1;
        }else {
            left = mid;
        }
    }
}

 解釋說明：

①while(left < right)

這樣查找結束的條件就是left == right，就不需要糾結返回left還是right。如果題意說明二分查找必有答案，直接返回即可；若二分查找可能沒有答案，也只需要在結尾作一下判斷就好。

②取中位數

mid = (rigth - left) >>> 1使用無符號右移的好處

a 位移操作符要比除法執行的快

b 無符號右移在高位補0，在除法移除的時候也能夠得到正確的答案

補充說明：

左移：低位補0；

邏輯右移（無符號右移）：高位補0；

算數右移（有符號右移）：高位補符號位

③在寫分支時，優先寫好想的、能夠排除mid的，難想的直接else

注意取左中位數 mid = (right - left)  >>> 1   要的對應left = mid + 1；

取有中位數 mid = (right - left + 1)  >>> 1 要對應right = mid - 1；

這樣可以有效的避免死循環。