二分查找法

• 对于有序数列，才能使用二分查找法(排序的作用)

package com.hoho.algorithms.binarysearch;
public class BinarySearch {
    public BinarySearch() {
    }
    public static <E extends Comparable<E>> int searchR(E[] data, E target) {
        return searchR(data, 0, data.length - 1, target);
    }
    /**
     * 递归
     */
    private static <E extends Comparable<E>> int searchR(E[] data, int l, int r, E target) {
        if (l > r) return -1;
        int mid = l + (r - l) / 2;
        if (data[mid].compareTo(target) == 0) return mid;
        if (data[mid].compareTo(target) < 0) return searchR(data, mid + 1, r, target);
        return searchR(data, l, mid - 1, target);
    }
    /**
     * 重点：非递归 关注查找的范围与每次变动时左右边界的取值
     */
    public static int binarySearch(Comparable[] arr, int n, Comparable target){
        int l = 0, r = n - 1; // 在[l...r]的范围里寻找target
        while(l <= r){    // 当 l == r时,区间[l...r]依然是有效的
            int mid = l + (r - l) / 2;
            if(arr[mid].compareTo(target) == 0) return mid;
            if(target.compareTo(arr[mid]) > 0)
                l = mid + 1;  // target在[mid+1...r]中; [l...mid]一定没有target
            else    // target < arr[mid]
                r = mid - 1;  // target在[l...mid-1]中; [mid...r]一定没有target
        }
        return -1;
    }
    /**
     * 更改边界范围
     */
        public static int binarySearch(Comparable[] arr, int n, Comparable target){
        int l = 0, r = n; // 在[l...r)的范围里寻找target
        while(l < r){    // 当 l == r 时, 区间[l...r)是一个无效区间
            int mid = l + (r - l) / 2;
            if(arr[mid].compareTo(target) == 0) return mid;
            if(target.compareTo(arr[mid]) > 0)
                l = mid + 1;  // target在[mid+1...r)中; [l...mid]一定没有target
            else    // target < arr[mid]
                r = mid;  // target在[l...mid)中; [mid...r)一定没有target
        }
        return -1;
    }
}