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

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;
    }

}