Java实现lowerBound及upperBound

拼搏现实的明天。 2022-07-28 04:25 135阅读 0赞

Java中已经实现了BinarySearch，但没有lowerBound和upperBound，整理一下其实现原理。  
折半查找中，寻求中间元素的下标时，使用的是“ int m = l + (r - l) / 2;”这种方法，这样做和“int m = (l + r)/2”的结果是一样的，但是避免了溢出，这可以通过下面的代码来验证。

public class Main {
    
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            int x = (Integer.MAX_VALUE + 10)/2;//在数学上，这两者的值是一样的，但是后者更为安全
            int y =10+ (Integer.MAX_VALUE - 10)/2;//避免溢出
            System.out.println(x+","+y);
        }
    
    }

运行结果：  
![这里写图片描述][20160330164455968]

lowerBound和upperBound的实现原理同折半查找相似，都是在区间中寻找元素。  
说明：**nums是非降序数组，当v在nums中存在时返回它出现的第一个位置；如果不存在，返回一个下标index，在此处插入v后，仍然使nums中的数字保持有序。**

//注意寻找的是下界！
    public static int lowerBound(int[] nums,int l,int r,int v){ 
            while(l<r){
                int m = l + (r - l) / 2;
                if(nums[m] >= v) r = m;//因为是寻找下界，不考虑右边还有没有元素
                else if(nums[m] < v) l = m+1;
            }
            return l;
    }

upperBound实现的功能是这样的：当v存在时返回它出现的最后一个位置的后面一个位置（注意，不是它的出现位置）。如果不存在，返回这样一个下标index：在此处插入v后序列仍然有序。

public static int upperBound(int[] nums,int l,int r,int v){
            while(l<r){
                int m = l + (r - l) / 2;
                if(nums[m] <= v) l = m+1;
                else if(nums[m] > v) r = m;
            }
            return l;
    }

[20160330164455968]: /images/20220727/6915878647c047e9b3b1cca2e2a64cad.png