二分查找有兩種實現(xiàn)方式：
遞歸實現(xiàn)，循環(huán)迭代實現(xiàn)，相比而言，迭代循環(huán)實現(xiàn)比較有難度

遞歸實現(xiàn)方式

public static int binarySearch(int[] param, int target) {

        if (param.length == 0) {
            return -1;
        }
        int middleIndex = param.length / 2;
        int middleValue = param[middleIndex];
        if (target == middleValue) {
            return target;
        }
        while (target != middleValue && target < middleValue) {
            int[] leftParam = Arrays.copyOfRange(param, 0, middleIndex);
            int result = binarySearch(leftParam, target);
            if (result == target) {
                return result;
            }else {
                return -1;
            }
        }
        while (target != middleValue && target > middleValue) {
            int[] rightParam = Arrays.copyOfRange(param, middleIndex + 1, param.length);
            int result = binarySearch(rightParam, target);
            if (result == target) {
                return result;
            }else {
                return -1;
            }
        }
        return -1;
    }

迭代實現(xiàn)方式

public static int binarySearch(int[] param, int target) {

        if (param.length == 0) {
            return -1;
        }
        int left = 0;
        int right = param.length-1;
        while (left<=right){
            int middle = left +(right-left)/2;
            if(target == param[middle]){
                return middle;
            }else if(target<param[middle]){
                right = middle-1;
            }else if(target>param[middle]){
                left = middle+1;
            }
        }
        return -1;
    }

二者的不同在于，遞歸方式每次切割一半的數(shù)組作為入?yún)?，從而縮小查找范圍
迭代方式改變索引搜索區(qū)間，每次左邊索引移動，或者右邊索引移動一個位置，縮小查詢的區(qū)間范圍

迭代法實現(xiàn)二分查找看似簡單，但細節(jié)很難把握，容易陷進坑里。到底是“<=” 還是“<” ,到底是arrays.length 還是arrays.length-1? 很容易搞暈。正如發(fā)明 KMP 算法的Knuth大佬說的：Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky...思維簡單很簡單，細節(jié)很磨人

下邊就抽絲剝繭，給你捋清楚：
1 while (left<=right) 處到底應該是left<=right還是left<right呢？首先要明白，<= 就等價于[1,2,3] 閉合區(qū)間，而< 就等價于[1,2,3）就是左閉右開的區(qū)間。所以首先搞清楚最后一位是否包閉合

2 right的值應該是param.length-1，還是param.length，決定了是否閉合 如果right=param.length 那么就應該是開區(qū)間，否則會索引越界，反之，如果right=param.length-1 那么while中就是閉區(qū)間，包含等號。即滿足這一條件的時候，還會進入while方法體，繼續(xù)執(zhí)行

3 為什么是left = mid+1; 因為while中的條件是閉合區(qū)間，所以本次搜索已經(jīng)驗證過mid位置處的值是否滿足，所以右半邊數(shù)組的起始索引就從下一位，即mid+1位置開始搜索。反之，如果搜索左半邊數(shù)組，就從上一位，mid-1位置，搜索左半邊位置，即right=mid-1;

4看完以后思路應該清晰了，但你會發(fā)現(xiàn)這個方法其實有很大的局限性，使用范圍有限。比如說給你有序數(shù)組 nums = [1,2,2,2,3]，target = 2，此算法返回的索引是 2，沒錯。但是如果我想得到 target 的左側邊界，即索引 1，或者我想得到 target 的右側邊界，即索引 3，這樣的話此算法是無法處理的。

這樣的需求很常見。常見的思路可能會想，找到一個 target 索引，然后向左或向右線性搜索不行嗎？可以，但不是很好，脫離了二分查找的精髓了，因為這樣難以保證二分查找對數(shù)級的復雜度了。

接下來通過一個案例所展示的技巧解決這個問題，讓這個算法具有真正的實用價值。跟著我來一起學習吧。

下邊是尋找左邊界的代碼

int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; // 注意

    while (left < right) { // 注意
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid;//原來這里會返回，但現(xiàn)在不返回，讓循環(huán)繼續(xù)
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}

1為什么 while(left < right) 而不是 <= ?
解答：這個問題應該不難回答了吧，因為right = nums.length 也就是索引越界的位置，所以應該是<左閉右開的區(qū)間形式，不包含最后一位
2 while(left < right) 終止的條件是 left == right，此時搜索區(qū)間 [left, left) 恰巧為空，所以可以正確終止，不再進入循環(huán)體中
3為什么沒有返回 -1 的操作？如果 nums 中不存在 target 這個值，怎么辦？這個需要一步步來，尤其要理解“左邊界”的特殊含義：

left_bound.png

nums數(shù)組中小于target=2的元素有1個
比如對于有序數(shù)組 nums = [3,4,5,6], target = 2，算法會返回 0，含義是：nums 中小于 2 的元素有 0 個。如果 target = 9，算法會返回 4，含義是：nums 中小于 8 的元素有 4 個

結合以上分析可以看出：返回的值（即left左邊界值）取值是閉區(qū)間[0,nums.length],所以我們簡單添加兩行代碼就能在正確的時候 return -1：

nums[left] == target? left：-1

4 left =mid+1,right=mid 這還是符合我們之前說的，左邊界右移，右邊界左移
5 為什么該算法能夠搜索左側邊界？
是下邊這段代碼

if (nums[mid] == target)
        right = mid;

這段代碼的意思就是將右邊界不斷替換為最新的mid值，而mid值是不斷減小的，在[left,mid) 位置上繼續(xù)搜索，這一點確實不容易想到，也是技巧所在了