二分查找的分析

朱雀 2023-06-19 11:02 68阅读 0赞

// 普通二分查找模板
        public static int find(int[] arr,int target) {
        
            int l = 0;
            int r = arr.length-1;
    
            while (l <= r) {
        
                int mid = (l + r) >>> 1;
                if (arr[mid] == target) {
        
                    return mid;
                } else if (arr[mid] > target) {
        
                    r = mid -1;
                } else {
        
                    l = mid + 1;
                }
            }
            return -1;
        }

优化的二分查找

// 改进的二分查找 出来二分不一样的情况
        /*
            使用这个的时候，要思考左，右边界，如果左右边界不包括目标数值，就会导致错误
            1.找到需要返回的区间   [ l .... r]，思考l ,r索引是有效，是我们需要返回的值吗？
            2.mid = (l + r)>>> 1， 拿到的mid
            如果在偶数数组中，分为左中位数和右中位数：
            int mid = l + (r - l )/2;   得到左中位数索引       中位数的选择是防止 在if选择中发生死循环
            int mid = l + (r - l +1 )/2  得到右中位数索引
            如果在奇数数组中，以上两者都能选到最中间的那个数
    
    
         */
        public int findNot(int[] arr,int target) {
        
            int l = 0;
            int r = arr.length-1;
    
            while (l < r) {
          // while里是 l < r ,===》 跳出循环时 l == r,返回l or r 结果一样
                int mid = (l + r) >>> 1;
                if (arr[mid] <= target) {
            //根据分支逻辑选择中位数的类型，可能是左中位数，也可能是右位数，选择的标准是避免死循环
                                            //1、如果分支的逻辑，在选择左边界的时候，不能排除中位数，那么中位数就选“右中位数”，只有这样区间才会收缩，否则进入死循环
                                            //2、同理，如果分支的逻辑，在选择右边界的时候，不能排除中位数，那么中位数就选“左中位数”，只有这样区间才会收缩，否则进入死循环。
                    r = mid;
                } else {
        
                    l = mid + 1;
                }
            }
            return l;
        }