二分查找及其变种

二分查找，也叫做折半查找。

二分查找是在已经拍好序的数组中，每次取中间值与待查关键字比较，如果中间位置的值笔待查关键字大，则在前半部分循环这个查找的过程，如果中间位置的值比待查关键字小，则在后半部分循环这个查找的过程。直到找到了为止，否则序列中没有待查的关键字。

public static int binarySearch(int[] arr, int k){
        int low = 0;
        int high = arr.length - 1;
        int mid;
        while(low <= high){
            mid = (low + high) >> 1;
            if(arr[mid] == k){
                return mid;
            }else if(arr[mid] > k){
                high = mid - 1;
            }else{
                low = mid + 1;
            }
        }
        return -1;
    }

也可以采用递归实现

public static int binarySearchByRecursion(int[] arr, int k, int low, int high){
        if(low < high){
            int mid = (low + high) >> 1;
            if(k == arr[mid]){
                return mid;
            }
            else if(k > arr[mid]){
                return binarySearchByRecursion(arr, k, mid + 1, high);
            }else{
                return binarySearchByRecursion(arr, k, low, mid - 1);
            }
        }
        return -1;
    }

变种1，假设数组中存在值相同的元素，找到第一个这个值出现的位置：

public static int binarySearchFirstElement(int[] arr, int k){
        int low = 0;
        int high = arr.length - 1;
        int mid;
        while(low < high){
            mid = (high + low) >> 1;
            if(arr[mid] < k){
                low = mid + 1;
            }else{
                high = mid;
            }
        }
        if(arr[low] != k){
            return -1;
        }else{
            return low;
        }
    }

变种2，条件同上，找到最后一个这个值出现的位置

public static int binarySearchLastElement(int[] arr, int k){
        int low = 0;
        int high = arr.length - 1;
        int mid;
        while(low < high){
            mid = (high + low + 1) >> 1;
            if(arr[mid] <= k){
                low = mid;
            }else{
                high = mid - 1;
            }
        }
        if(arr[low] != k){
            return -1;
        }else{
            return high;
        }
    }