算法与数据结构01：二分法

• 普通二分查找
• 在有序数组中查找大于等于某个数的最左侧位置
• 在有序数组中查找小于等于某个数的最右侧位置
• 寻找局部最小

public class BinarySearch01 {

    public static int search(int[] arr, int num) {
        if (arr == null || arr.length == 0) return -1;
        int l = 0;
        int r = arr.length - 1;
        int mid;
        while (l <= r) {
            mid = l + ((r - l) >> 1);
            if (arr[mid] > num) r = mid - 1;
            else if (arr[mid] < num) l = mid + 1;
            else return mid;
        }
        return -1;
    }

}

public class BinarySearch02 {

    public static int search(int[] arr, int num) {
        if (arr == null || arr.length == 0) return -1;
        int l = 0;
        int r = arr.length - 1;
        int index = -1;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (arr[mid] >= num) {
                index = mid; // arr[mid]是目前已知的大于等于num的最左侧位置
                r = mid - 1; // 排查mid右边的数
            } else l = mid + 1; // mid以及mid左边的数都比num小，排查mid以及mid左边的数
        }
        return index;
    }

}

public class BinarySearch03 {

    public static int search(int[] arr, int num) {
        if (arr == null || arr.length == 0) return -1;
        int l = 0;
        int r = arr.length - 1;
        int index = -1;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (arr[mid] > num) r = mid - 1; //mid以及mid右侧都是大于num的数，都排除
            else {
                index = mid; // 目前已知的小于等于num的最右侧位置
                l = mid + 1; // 排除左边的数
            }
        }
        return index;
    }

}

public class BinarySearch04 {

    public static int search(int[] arr) {
        if (arr == null || arr.length == 0) return -1;
        if (arr.length == 1) return 0;

        //arr[0] < arr[1]，所以arr[0]满足局部最小，返回0
        if (arr[0] < arr[1]) return 0;

        //arr[arr.length - 1] < arr[arr.length - 2]，所以arr[arr.length - 1]满足局部最小，返回arr.length - 1
        if (arr[arr.length - 1] < arr[arr.length - 2]) return arr.length - 1;

        //此时l~r范围内，arr[l] > arr[l+1] 趋势递减，arr[arr.length-2] < arr[arr.length-1]趋势递增
        //中间必有最小值
        int l = 1;
        int r = arr.length - 2;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            //找到局部最小，返回
            if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) return mid;
            //如果arr[mid] > arr[mid - 1]，则arr[mid-1] < arr[mid]，趋势递增，l~mid中间必有最小值
            //r赋值为mid-1
            else if (arr[mid] > arr[mid - 1]) r = mid - 1;
            //arr[mid]小于arr[mid-1]，只能排除左边的一部分，从右边的一部分寻找局部最小
            else l = mid + 1;
        }
        return -1;
    }

}