二分查找算法

一、算法

二分查找算法非常简单，但是又个致命的问题，就是 right 不知道如何赋值，以及 while 循环的条件是什么。很简单，只需要举一个简单的例子。

假设数组为：[1,2,3,4,5]。

现在需要查找 5，能找到：
如果应该令 left = 0，right = arr.length - 1，那么 while(left <= right)，应该只有 left = right 的位置，才能算出来 mid = 4，才能找到相应的数字。

 public int binarySearch(int[] arr, int target){
        int left = 0, right = arr.length - 1;
        while (left <= right){
            int mid = (left + right) >> 1;
            if(arr[mid] == target){
                return mid;
            }else if(arr[mid] > target){
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }

        return -1;
    }

需要查找6，数组里没有6，应该返回 -1：
如果应该令 left = 0，right = arr.length，那么 while(left < right)，因为6不存在，left == right 就会越界报错。

 public int binarySearch(int[] arr, int target){
        int left = 0, right = arr.length;
        while (left < right){
            int mid = (left + right) >> 1;
            if(arr[mid] == target){
                return mid;
            }else if(arr[mid] > target){
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }

        return -1;
    }