算法|1.二分及其扩展

缺乏、安全感 2024-03-16 09:15 35阅读 0赞

## 算法|1.二分及其扩展 ##

### 1、有序数组中找到num ###

题意：给定有序数组，在有序数组中找到指定数字，找到返回true，找不到返回false.

解题思路：

*  数组有序查找指定元素使用二分法
 *  L指针初始值设为0，R指针初始值设为arr.length-1，属于左闭右闭的区间，循环条件为L<=R

优化的点：

*  求平均值使用有符号右移：mid=left+((right-left)>>1).好处有两点1.防止溢出2.提高效率

对数器：

*  使用顺序遍历
 *  前提：生成随机数组

核心代码：

public static boolean exist(int[] arr,int num){
        
        int L=0;
        int R=arr.length-1;
        int M=L+((R-L)>>1);
        while(L<=R){
        
            if(arr[M]<num){
        
                L=M+1;
            }else if(arr[M]>num){
        
                R=M-1;
            }else{
        
                return true;
            }
            M=L+((R-L)>>1);
        }
        return false;
    }

测试代码：

//for test
        public static boolean test(int[] arr,int num){
        
            for (int cur:arr) {
        
                if(cur==num){
        
                    return true;
                }
            }
            return false;
        }
        //for test
        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+1)*Math.random());
            }
            return arr;
        }
    
        //for test
        public static void print(int[] arr){
        
            for (int cur:arr) {
        
                System.out.print(cur+" ");
            }
            System.out.println();
        }
    //    //for test
        public static void main(String[] args) {
        
            int testTime=1000;
            int maxSize=10;
            int maxValue=100;
            boolean succeed=true;
            for (int i = 0; i < testTime; i++) {
        
                int[] arr=generateRandomArray(maxSize,maxValue);
                int num=(int) ((maxValue+1)*Math.random());
    
                //使用前提：数组是有序的
                Arrays.sort(arr);
    
                boolean ret1=exist(arr,num);
                boolean ret2=test(arr,num);
                if(ret1!=ret2){
        
                    print(arr);
                    System.out.println("num:"+num);
                    System.out.println("exist:"+ret1);
                    System.out.println("test:"+ret2);
                    System.out.println("Oops!Error!");
                    succeed=false;
                    break;
                }
            }
            if(succeed==true){
        
                System.out.println("succeed!");
            }
        }

测试结果：

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0HyhetxX-1685076234668)(F:\\typora插图\\image-20230526103704932.png)\]][img-0HyhetxX-1685076234668_F_typora_image-20230526103704932.png]

> 果然，人长时间不写代码，脑子是会秀逗的（…）
> 
> 你敢信这是一开始写的？？真该死啊…
> 
>     public static boolean exist(int[] arr,int num){
>          
>         int L=0;
>         int R=arr.length-1;
>         int M=L+((R-L)>>1);
>         while(L<=R){
>          
>             if(arr[L]<num){
>          
>                 L=M+1;
>             }else if(arr[R]>num){
>          
>                 R=M-1;
>             }else{
>          
>                 return true;
>             }
>             M=L+((R-L)>>1);
>         }
>         return false;
>     }
> 
> 还debug半天反应不过来
> 
>     //for test
>         //1.使用前提：必须是有序的
>         //2.sort排序不生效——得是M和Num比啊！！！
>     //    public static void main(String[] args) {
>          
>     //        int[] arr={-15, -14 ,4 ,24, 26, 33, 81  };
>     //        Arrays.sort(arr);
>     //        if(exist(arr,4)!=test(arr,4)){
>          
>     //            System.out.println(false);
>     //        }else{
>          
>     //            System.out.println(true);
>     //
>     //        }
>     //    }

### 2、有序数组中找到>=num的最左边的位置 ###

题意：给定有序数组，在有序数组中找到>=指定数字的最左边的下标，找到返回对应值，找不到返回-1.

解题思路：

*  注意：这里并没有要求value值必须存在于指定数组
 *  数组有序查找指定元素下标使用二分法
 *  在原来的基础上增加一个变量记录当前查找元素下标，如果当前值大于等于指定值，则记录下标。最终返回的结果只可能是两种值-1，符合题意的值

优化思路：

*  没有采用在上一题的基础上增加变量记录当前坐标，然后再对这个坐标进行操作，而是直接在分支条件上动手，记录并迭代更新，这样只需要在返回处进行判断是否存在这样的值即可。

对数器：

*  顺序遍历

核心代码：

public static int nearestIndex(int[] arr,int num){
        
        int L=0;
        int R=arr.length-1;
        int M=L+((R-L)>>1);
        int index=-1;
        while(L<=R){
        
            if(arr[M]>=num){
        
                index=M;
                R=M-1;
            }else{
        
                L=M+1;
            }
            M=L+((R-L)>>1);
        }
        return index;
    }

测试代码：

基本同上，但是需要修改比对方法和核心方法的返回值

//for test
    public static int test(int[] arr,int num){
        
        for (int i = 0; i < arr.length; i++) {
        
            if(arr[i]>=num){
        
                return i;
            }
        }
        return -1;
    }
    //for test
    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+1)*Math.random());
        }
        return arr;
    }
    
    //for test
    public static void printArray(int[] arr){
        
        for (int cur:arr) {
        
            System.out.print(cur+" ");
        }
        System.out.println();
    }
    //    //for test
    public static void main(String[] args) {
        
        int testTime=1000;
        int maxSize=10;
        int maxValue=100;
        boolean succeed=true;
        for (int i = 0; i < testTime; i++) {
        
            int[] arr=generateRandomArray(maxSize,maxValue);
            int num=(int) ((maxValue+1)*Math.random());
    
            //使用前提：数组是有序的
            Arrays.sort(arr);
    
            int ret1=nearestIndex(arr,num);
            int ret2=test(arr,num);
            if(ret1!=ret2){
        
                printArray(arr);
                System.out.println("num:"+num);
                System.out.println("nearestIndex:"+ret1);
                System.out.println("test:"+ret2);
                System.out.println("Oops!Error!");
                succeed=false;
                break;
            }
        }
        if(succeed==true){
        
            System.out.println("succeed!");
        }
    }

测试结果：

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NOHyBbMu-1685076234669)(F:\\typora插图\\image-20230526110446203.png)\]][img-NOHyBbMu-1685076234669_F_typora_image-20230526110446203.png]

### 3、有序数组中找到<=num最右的位置 ###

题意：给定有序数组，在有序数组中找到<=指定数字的最右边的下标，找到返回对应值，找不到返回-1.

解题思路：

*  数组有序，查找指定元素下标==>二分
 *  在分支条件上动手

优化思路：

*  在分支条件上动手，同上题，合并两个分支条件，index初值设为-1

核心代码：

public static int nearestIndex(int[] arr,int num){
        
        int L=0;
        int R=arr.length-1;
        int M=L+((R-L)>>1);
        int index=-1;
        while(L<=R){
        
            if(arr[M]<=num){
        
                index=M;
                L=M+1;
            }else{
        
                R=M-1;
            }
            M=L+((R-L)>>1);
        }
        return index;
    }

测试代码：

基本同上，但是注意这次对数器方法需要倒序遍历，找到返回，找不到返回-1

//for test
    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;
    }
    //for test
    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+1)*Math.random());
        }
        return arr;
    }
    
    //for test
    public static void printArray(int[] arr){
        
        for (int cur:arr) {
        
            System.out.print(cur+" ");
        }
        System.out.println();
    }
    //    //for test
    public static void main(String[] args) {
        
        int testTime=1000;
        int maxSize=10;
        int maxValue=100;
        boolean succeed=true;
        for (int i = 0; i < testTime; i++) {
        
            int[] arr=generateRandomArray(maxSize,maxValue);
            int num=(int) ((maxValue+1)*Math.random());
    
            //使用前提：数组是有序的
            Arrays.sort(arr);
    
            int ret1=nearestIndex(arr,num);
            int ret2=test(arr,num);
            if(ret1!=ret2){
        
                printArray(arr);
                System.out.println("num:"+num);
                System.out.println("nearestIndex:"+ret1);
                System.out.println("test:"+ret2);
                System.out.println("Oops!Error!");
                succeed=false;
                break;
            }
        }
        if(succeed==true){
        
            System.out.println("succeed!");
        }
    }

测试结果：

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-A9n5RfAR-1685076234670)(F:\\typora插图\\image-20230526110946676.png)\]][img-A9n5RfAR-1685076234670_F_typora_image-20230526110946676.png]

### 4、局部最小值 ###

题意：给定一个数组，已知任一相邻的数都不相等，找到随便一个局部最小值返回。

局部最小值定义：

定义何为局部最小值：
    arr[0] < arr[1]，0位置是局部最小；
    arr[N-1] < arr[N-2]，N-1位置是局部最小；
    arr[i-1] > arr[i] < arr[i+1]，i位置是局部最小；

解题思路：

*  注意：1.是下标不是值**2.边界条件判断：空数组、长度为1的数组、两端判断、中间判断，一共四部分逻辑处理！！！**
 *  闭存在与不存在：是不是存在“凹”结构
 *  需要有左右两边淘汰的逻辑，使用二分
 *  遍历范围为可能成为局部最小值的位置：边界位置只需要比较一个位置而中间位置需要比较两个位置，为了统一处理，**边界符合条件时单独判断**，中间位置使用L、R、M三个指针进行遍历
 *  （大体）分支条件的判断从原来的M下标和num比，改成M和M-1及M和M+1比较，两个需要调整的条件都是>，反之就是符合条件的局部最小值
 *  （具体到某个分支）每次判断都是为砍范围，缩小范围与另外一边重新构成凹结构，砍到没法再砍了，直接返回对应下标（多结合实例）  
    ![在这里插入图片描述][9d861dfc45c049b68bb47fdf9c9e6bac.jpeg_pic_center]

优化思路：

*  使用二分法，运用左右淘汰的逻辑
 *  每次三次比较到经典二分三次比较的套用

对数器：

*  遍历？错
    
    可能存在多个局部最小值，所以不能通过比对返回的下标，而是拿着下标去验证是不是！！
    
    当然再次之前需要判断下标是否合法
    
    这里的对数器可以命名为isRight，返回值为布尔类型
    
    优化
    
     *  可以根据index分类讨论：中间有效性、两端有效性
     *  中间index判断可以用三目表达式

核心代码：

> 注意调整新三分支中的调整条件：
> 
> Q1：每次怎么调整？既然没有要求数组有序，那是不是只要mid可以改变就可以，是不是L=M+1和R=M-1的调整条件可以交换？
> 
> 不是！！
> 
> 经过开头的预处理，说明该数组上一定存在“凹”结构，那么如果M左边的位置小于它，那么就破坏了整体的这个结构，我们就从右边找,此时右边的结构满足，对应的左边的结构满足，每次把破坏结构的一半砍下去，也一定能够找出来。
> 
> Q2：这样一定能找出结果吗？
> 
> 能的，这是一个算法的结论：即不存在相同元素的数组，一定存在局部最小值

public static int getLessIndex(int[] arr){
        
        if(arr==null||arr.length==0){
        
            return -1;
        }
        if(arr.length==1||arr[0]<=arr[1]){
        
            return 0;
        }
        if(arr[arr.length-1]<=arr[arr.length-2]){
        
            return arr.length-1;
        }
        int L=1;
        int R=arr.length-2;
        int M=L+((R-L)>>1);
        while(L<=R){
        
            if(arr[M]>arr[M-1]){
        //砍左边
                R=M-1;
            }else if(arr[M]>arr[M+1]){
        //砍左边
                L=M+1;
            }else{
        
                return M;
            }
            M=L+((R-L)>>1);
        }
        return -1;
    }

测试代码：

*  数组不需要严格有序
 *  数组中不能有重复元素——赋值时做一个do while循环

//for test
    public static boolean isRight(int[] arr,int index){
        
        if(arr.length<=1){
        
            return true;
        }
        if(index==0){
        
            return arr.length==1||arr[0]<arr[1];
        }
        if(index==arr.length-1){
        
            return arr[index]<arr[index-1];
        }
        return arr[index] < arr[index - 1] && arr[index] < arr[index + 1];
    }
    //for test
    public static int[] generateRandomArray(int maxSize,int maxValue){
        
        int[] arr=new int[(int) ((maxSize+1)*Math.random())+1];
        arr[0]= (int) ((maxValue+1)*Math.random())-(int) ((maxValue+1)*Math.random());
        for (int i = 1; i < arr.length; i++) {
        
            do {
        
                arr[i]= (int) ((maxValue+1)*Math.random())-(int) ((maxValue+1)*Math.random());
            }while(arr[i]==arr[i-1]);
        }
        return arr;
    }
    
    //for test
    public static void printArray(int[] arr){
        
        for (int cur:arr) {
        
            System.out.print(cur+" ");
        }
        System.out.println();
    }
    //for test
    public static void main(String[] args) {
        
        int testTime=1000;
        int maxSize=10;
        int maxValue=100;
        boolean succeed=true;
        for (int i = 0; i < testTime; i++) {
        
            int[] arr=generateRandomArray(maxSize,maxValue);
    
            int index=getLessIndex(arr);
            if(!isRight(arr,index)){
        
                printArray(arr);
                System.out.println("getLessIndex:"+index);
                System.out.println("Oops!Error!");
                succeed=false;
                break;
            }
        }
        if(succeed==true){
        
            System.out.println("succeed!");
        }
    }

测试结果：

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HLlEoZ5m-1685076234670)(F:\\typora插图\\image-20230526123206885.png)\]][img-HLlEoZ5m-1685076234670_F_typora_image-20230526123206885.png]

### 二分法总结 ###

**算法描述**：不断对闭区间（其实有时候处理的是半开半闭区间、开区间）一分为二的方法。

**基本思想**：一分为二

**使用场景：**

*  有序数组查找指定元素/下标
 *  无序数组（满足左右淘汰逻辑）查找指定元素/下标

**例题总结：**

*  有序数组查找指定元素：数组必须预处理保证有序，三分支均为arr\[M\]与num比较，调整放到分支外
 *  有序数组查找>=num最左边的位置：即查找数组中大于等于num的最小值的下标。其中一和arr\[M\]>num分支合并，不断更新,更新方向R=M-1
 *  有序数组查找<=num最右边的位置：即查找数组中小于等于num的最大值的下标。其中一和arr\[M\]<num分支合并，不断更新，更新方向L=M+1
 *  局部最小值：空数组、长度为1的数组、两端判断、中间判断，一共四部分逻辑处理，缩小范围的调整结合趋势图分析，实在不行再看运行结果

[img-0HyhetxX-1685076234668_F_typora_image-20230526103704932.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/6e3ed722b7e742beb991178146705aa2.png
[img-NOHyBbMu-1685076234669_F_typora_image-20230526110446203.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/99731be6db774afaa67cab53ba6bef82.png
[img-A9n5RfAR-1685076234670_F_typora_image-20230526110946676.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/ade6f961135c455d9f97346c37cbb25b.png
[9d861dfc45c049b68bb47fdf9c9e6bac.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/9fad522bb4cd44e0a5c88d96921f8692.png
[img-HLlEoZ5m-1685076234670_F_typora_image-20230526123206885.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/81ab6f263fac48f58d9c0f4e5977c625.png