二分查找,就是在有序的线性表中查找特定元素,每次查找时直接比较中间元素,如果中间元素比目标值大,就往左侧区间找;如果中间元素比目标值小,就往右侧区间找;如果相等,说明找到了!

public static int search(int[] arr, int target){
    int lo = 0, hi = arr.length - 1;
    int mid = 0;
    while (lo <= hi) {
        mid = lo + ((hi - lo) >> 1);
        if (arr[mid] > target) {
            hi = mid - 1;
        } else if (arr[mid] < target) {
            lo = mid + 1;
        }else{
            return mid;
        }
    }
    return -1;
}

但是呢,它的查找非常容易错,就是在一些变形问题上,比如查找第一个等值的元素、最后一个等值元素、第一个大于等于值的元素、最后一个小于等于值的元素。下面贴一下代码,以后可以复看。

我觉得现在学到一个技巧:不追求完美的写法,把逻辑写清楚就行。

public class Search {
    public static void main(String[] args) {
        int[] arr = {
                1, 3, 4, 5, 6, 8, 8, 8, 8, 9, 12
        };
        System.out.println(search(arr, 3));
        System.out.println(searchLeft(arr, 8));
        System.out.println(searchRight(arr, 8));
        System.out.println(searchFirstGreaterValue(arr, 7));
        System.out.println(searchLastLesserValue(arr, 7));
    }

    public static int search(int[] arr, int target){
        int lo = 0, hi = arr.length - 1;
        int mid = 0;
        while (lo <= hi) {
            mid = lo + ((hi - lo) >> 1);
            if (arr[mid] > target) {
                hi = mid - 1;
            } else if (arr[mid] < target) {
                lo = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
    }

    public static int searchLeftShort(int[] arr, int target) {
        int lo = 0, hi = arr.length - 1;
        int mid = 0;
        while (lo <= hi) {
            mid = lo + ((hi - lo) >> 1);
            if (arr[mid] >= target) {
                hi = mid - 1;
            } else if (arr[mid] < target) {
                lo = mid + 1;
            }
        }
        // 跳出循环的时候再测
        if (lo < arr.length && arr[lo] == target) {
            return lo;
        }
        return -1;
    }

    public static int searchLeft(int[] arr, int target) {
        int lo = 0, hi = arr.length - 1;
        int mid = 0;
        while (lo <= hi) {
            mid = lo + ((hi - lo) >> 1);
            if (arr[mid] > target) {
                hi = mid - 1;
            } else if (arr[mid] < target) {
                lo = mid + 1;
            } else {
                // 看看前一个是否是目标值,也是,就说明还没有找到最左一个
                if (mid == 0 || arr[mid - 1] != target) {
                    return mid;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return -1;
    }

    public static int searchRight(int[] arr, int target) {
        int lo = 0, hi = arr.length - 1;
        int mid = 0;
        while (lo <= hi) {
            mid = lo + ((hi - lo) >> 1);
            if (arr[mid] > target) {
                hi = mid - 1;
            } else if (arr[mid] < target) {
                lo = mid + 1;
            } else {
                if (mid == arr.length - 1 || arr[mid + 1] != target) {
                    return mid;
                } else {
                    lo = mid + 1;
                }
            }
        }
        return -1;
    }

    public static int searchFirstGreaterValue(int[] arr, int target) {
        int lo = 0, hi = arr.length - 1;
        int mid = 0;
        while (lo <= hi) {
            mid = lo + ((hi - lo) >> 1);
            if (arr[mid] >= target){
                if (mid == 0 || arr[mid - 1] < target){
                    return mid;
                }
                hi = mid - 1;
            }else{
                lo = mid + 1;
            }
        }
        return -1;
    }

    public static int searchLastLesserValue(int[] arr, int target){
        int lo = 0, hi = arr.length - 1;
        int mid = 0;
        while (lo <= hi) {
            mid = lo + ((hi - lo) >> 1);
            if (arr[mid] > target){
                hi = mid - 1;
            }else{
                if (mid == arr.length - 1 || arr[mid + 1] > target){
                    return mid;
                }
                lo = mid + 1;
            }
        }
        return -1;
    }

}