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

}

在有序数组中查找大于等于某个数的最左侧位置

二分法不仅可以用于寻找某个指定的值，还可以寻找每个值出现的最左或最右位置，但是这种二分就不是寻找到指定的值就返回，而是继续二分，直到二分尽为止

/**
 * 二分查找大于等于某个数的最左侧位置
 * 如：数组 000111222333，num 1
 * 则返回的下标为3
 */
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;
    }

}

在有序数组中查找小于等于某个数的最右侧位置

/**
 * 二分查找小于等于某个数的最右侧位置
 * 如：数组 000111222333，num 5
 * 则返回的下标为3
 */
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;
    }

}

寻找局部最小

不一定是有序的数组才能二分，只要找到一种规律，可以一次排除掉一半的数据，就可以做二分

/**
 * 寻找局部最小
 * arr数组无序，并且相邻两个数不相等，从中找出一个局部最小的数，并返回下标
 * 局部最小：
 * 比如下标为i的数，如果小于小标i-1和i+1的数，则下标为i的数就是局部最小
 * 如果下标为0的数，小于下标为1的数，则下标为0的数就是局部最小
 * 如果下标为arr.length-1的数，小于arr.length-2的数，则arr.length-1的数就是局部最小
 */
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;
    }

}