阅读 29 SEO

算法 | 二分法

在数据结构书籍中,在介绍二分法时,常常会加上有序这个前提条件,其中有序的定义要麽是从大到小排序,要麽是从小到大排序。

那么,有序真的是所有问题求解时使用二分的必要条件吗?
答案是:不

只要正确构建左右两侧的淘汰逻辑,你就可以使用二分法,那我们现在通过以下例子来了解二分法。

1、在一个有序数组中,找某个数是否存在
2、在一个有序数组中,找>=某个数最左侧的位置
3、在一个有序数组中,找<=某个数最右侧的位置
4、局部最小值问题

在一个有序数组中,找某个数是否存在

public static boolean exist(int[] sortedArr, int num) {
        if (sortedArr == null || sortedArr.length == 0) {
            return false;
        }
        int L = 0;
        int R = sortedArr.length - 1;
        int mid = 0;
        // L..R 至少两个数的时候
        while (L < R) { 
            mid = L + ((R - L) >> 1);
            if (sortedArr[mid] == num) {
                return true;
            } else if (sortedArr[mid] > num) {
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return sortedArr[L] == num;
    }

在一个有序数组中,找某个数是否存在.png

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

public static int nearestIndex(int[] arr, int value) {
        int L = 0;
        int R = arr.length - 1;
        int index = -1; // 记录最左的对号
        while (L <= R) { // 至少一个数的时候
            int mid = L + ((R - L) >> 1);
            if (arr[mid] >= value) {
                index = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return index;
    }

在一个有序数组中,找大于等于某个数最左侧的位置 .png

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

public static int nearestIndex(int[] arr, int value) {
        int L = 0;
        int R = arr.length - 1;
        int index = -1; // 记录最右的对号
        while (L <= R) {
            int mid = L + ((R - L) >> 1);
            if (arr[mid] <= value) {
                index = mid;
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        return index;
    }

在一个有序数组中,找小于等于某个数最右侧的位置 .png

局部最小值问题

public static int getLessIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1; // no exist
        }
        if (arr.length == 1 || arr[0] < arr[1]) {
            return 0;
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }
        int left = 1;
        int right = arr.length - 2;
        int mid = 0;
        while (left < right) {
            mid = (left + right) / 2;
            if (arr[mid] > arr[mid - 1]) {
                right = mid - 1;
            } else if (arr[mid] > arr[mid + 1]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return left;
    }

局部最小可以使用二分法完成,定义局部最小时隐含的规律即:一个不存在相同元素的数组一定存在局部最小值,因为只需要找到一个局部最小值,这样就可以使用二分查找将数组规模逐渐减小。
1、首先判断数组第一个值是否小于右边的值,若小于,则局部最小值为第一个数;否则进行下一步;
2、判断数组的最后一个值是否小于左边的值,若小于,则局部最小值为最后一个数;否则进行下一步;
3、通过二分法来验证除首位和末尾位置的数组数据的局部最小值,若某值左右两边的值都大于该值,那么该值就属于局部最小值;否则继续通过二分法进行查找。

文章分类
后端
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 gxwowoo@163.com 举报,一经查实,本站将立刻删除。
相关推荐