栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

【数据结构】二分法

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【数据结构】二分法

文章目录
  • 1. 从有序数组中找出 num
  • 2. 有序数组中找到 >=num 最左的位置
  • 3. 有序数组中找到 >=num 最左的位置
  • 4. 局部最小值问题

1. 从有序数组中找出 num
public class Code04_BSExist {

    public static boolean exist(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return false;
        }

        int l = 0, r = arr.length - 1;
        while (l <= r) {
            // (l + r) / 2 可能会溢出
            int mid = (r - l) / 2 + l;
            if (arr[mid] == num) {
                return true;
            } else if (arr[mid] > num) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        return false;
    }

    
    public static boolean test(int[] arr, int num) {
        for (int val : arr) {
            if (val == num) {
                return true;
            }
        }

        return false;
    }

    
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }

        Arrays.sort(arr);
        return arr;
    }

    public static void main(String[] args) {
        int testTimes = 500000;
        int maxSize = 10;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTimes; i++) {
            int[] arr = generateRandomArray(maxSize, maxValue);

            int num = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
            if (test(arr, num) != exist(arr, num)) {
                succeed = false;
                break;
            }
        }

        System.out.println(succeed ? "Nice!" : "Oh no!");
    }
}
2. 有序数组中找到 >=num 最左的位置
public class Code05_BSNearLeft {

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

        // 记录 ans 位置
        int res = -1;
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int mid = (r - l) / 2 + l;
            if (arr[mid] >= num) {
                res = mid;
                // 有可能 mid 的左侧还有 >=m 的值
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        return res;
    }

    
    public static int test(int[] arr, int num) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] >= num) {
                return i;
            }
        }

        return -1;
    }

    
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }

        Arrays.sort(arr);
        return arr;
    }

    public static void main(String[] args) {
        int testTimes = 500000;
        int maxSize = 10;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTimes; i++) {
            int[] arr = generateRandomArray(maxSize, maxValue);

            int num = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
            if (test(arr, num) != mostLeftNoLessNumIndex(arr, num)) {
                succeed = false;
                break;
            }
        }

        System.out.println(succeed ? "Nice!" : "Oh no!");
    }
}
3. 有序数组中找到 >=num 最左的位置
public class Code05_BSNearRight {

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

        // 记录 ans 位置
        int res = -1;
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int mid = (r - l) / 2 + l;
            if (arr[mid] <= num) {
                res = mid;
                // 有可能 mid 的左侧还有 >=m 的值
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        return res;
    }

    
    public static int test(int[] arr, int num) {
        for (int i = arr.length - 1; i >= 0; i--) {
            if (arr[i] <= num) {
                return i;
            }
        }

        return -1;
    }

    
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }

        Arrays.sort(arr);
        return arr;
    }

    public static void main(String[] args) {
        int testTimes = 500000;
        int maxSize = 10;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTimes; i++) {
            int[] arr = generateRandomArray(maxSize, maxValue);

            int num = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
            if (test(arr, num) != mostRightNoThanNumIndex(arr, num)) {
                succeed = false;
                break;
            }
        }

        System.out.println(succeed ? "Nice!" : "Oh no!");
    }
}
4. 局部最小值问题

1)数组第一个元素比第二个元素小,即为局部最小值。

2)数组最后一个元素比它前一个元素小,即为局部最小值。

3)若不满足,那么局部最小值必可在数组首尾两元素之间的某个位置取得。此时可以采用二分法思想,看中间位置是否符合条件,不符合就分成两部分,从不符合的那一边继续操作。

package lyb.class1;


public class Code06_BSAwesome {

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

        if (arr.length == 1) {
            return 0;
        }

        if (arr[0] < arr[1]) {
            return 0;
        }

        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }

        int l = 0, r = arr.length - 1;
        // 保有三个数进行判断
        while (l < r - 1) {
            int mid = (r - l) / 2 + l;
            if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
                return mid;
            } else {
                // mid - 1 > mid  mid > mid + 1
                // mid - 1 < mid  mid < mid + 1
                // mid - 1 < mid  mid > mid + 1
                if (arr[mid] > arr[mid - 1]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
        }

        return arr[l] < arr[r] ? l : r;
    }

    
    public static int[] generateRandomArray(int maxLen, int maxValue) {
        int[] arr = new int[(int) (Math.random() * maxLen) + 1];
        arr[0] = (int) (Math.random() * maxValue);
        for (int i = 1; i < arr.length; i++) {
            do {
                arr[i] = (int) (Math.random() * maxValue);
            } while (arr[i] == arr[i - 1]);
        }

        return arr;
    }

    
    public static boolean test(int[] arr, int index) {
        int l = index - 1;
        int r = index + 1;

        boolean left = l >= 0 ? arr[l] > arr[index] : true;
        boolean right = r < arr.length ? arr[r] > arr[index] : true;

        return left && right;
    }

    public static void main(String[] args) {
        int testTimes = 500000;
        int maxSize = 10;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTimes; i++) {
            int[] arr = generateRandomArray(maxSize, maxValue);

            int index = oneMinIndex(arr);
            if (!test(arr, index) ) {
                succeed = false;
                break;
            }
        }

        System.out.println(succeed ? "Nice!" : "Oh no!");
    }
}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/986202.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号