• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

二分查找的边界情况

开发技术 开发技术 2周前 (04-29) 7次浏览

一、手写二分的几种边界情况

1.普通查找值,找到即返回,不考虑位置

    //1.普通二分:查找数存不存在或者随便找一个
    public static int binarySearchOne(int target){
        int l=0,r=n-1,m;
        while(l<=r){
            m=(l+r)/2;
            if( a[m]<target ){
                l=m+1;
            }else if( a[m]>target ){
                r=m-1;
            }else
                return m;
        }
        return -1;
    }

2.找最后一个小于target的数

    // 2.找最后一个小于target的数
    public static int binarySearchLastLess(int target){
        int l=0,r=n-1,m;
        while(l<=r){
            m=(l+r)/2;
            if( a[m]>=target )
                r=m-1;
            else
                l=m+1;
        }
        return r<0?-1:r;
    }

3.找最后一个小于等于target的数

    // 3.找最后一个小于等于target的数
    public static int binarySearchLastLessEquals(int target){
        int l=0,r=n-1,m;
        while (l<=r){
            m=(l+r)/2;
            if( a[m]>target )
                r=m-1;
            else
                l=m+1;
        }
        return r<0?-1:r;
    }

4.找第一个大于target的数

    // 4.找第一个大于target的数
    public static int binarySearchFirstMore(int target){
        int l=0,r=n-1,m;
        while(l<=r){
            m=(l+r)/2;
            if( a[m]<=target )
                l=m+1;
            else
                r=m-1;
        }
        return l>=n?-1:l;
    }

5.找第一个大于等于目标值的数

    // 5.找第一个大于等于目标值的数
    public static int binarySearchFirstMoreEquals(int target){
        int l=0,r=n-1,m;
        while(l<=r){
            m=(l+r)/2;
            if( a[m]<target )
                l=m+1;
            else
                r=m-1;
        }
        return l>=n?-1:l;
    }

6.用l+(r-l)/2防止(l+r)/2溢出的情况和上述方法测试

二分查找的边界情况二分查找的边界情况

public class  BinaryTest{
    static int[] a=new int[15];
    static int n= a.length;
    public static void main(String[] args) {
        for(int i=0;i<n;i++)
            a[i]=i;
        a[1]=a[3]=a[4]=2;
        a[8]=a[10]=a[11]=a[12]=9;
        /**
         id  0 1 2 3 4 5 6 7 8 9  10  11  12  13  14
         val 0 2 2 2 2 5 6 7 9 9   9  9   9   13  14
         */
        System.err.println("普通二分查找4,返回的下标是"+binarySearchOne(4));
        System.err.println("普通二分查找2,返回的下标是"+binarySearchOne(2));
        System.err.println("普通二分查找7,返回的下标是"+binarySearchOne(7));
        System.err.println("普通二分查找9,返回的下标是"+binarySearchOne(9));
        System.err.println("---------------------------------");
        System.err.println("找最后一个小于0的数,返回的下标是"+binarySearchLastLess(0));
        System.err.println("找最后一个小于2的数,返回的下标是"+binarySearchLastLess(2));
        System.err.println("找最后一个小于5的数,返回的下标是"+binarySearchLastLess(5));
        System.err.println("找最后一个小于13的数,返回的下标是"+binarySearchLastLess(13));
        System.err.println("---------------------------------");
        System.err.println("找最后一个小于等于-1的数,返回的下标是"+binarySearchLastLessEquals(-1));
        System.err.println("找最后一个小于等于0的数,返回的下标是"+binarySearchLastLessEquals(0));
        System.err.println("找最后一个小于等于2的数,返回的下标是"+binarySearchLastLessEquals(2));
        System.err.println("找最后一个小于等于9的数,返回的下标是"+binarySearchLastLessEquals(9));
        System.err.println("找最后一个小于等于100的数,返回的下标是"+binarySearchLastLessEquals(100));
        System.err.println("---------------------------------");
        System.err.println("找第一个大于-11的数,返回的下标是"+binarySearchFirstMore(-11));
        System.err.println("找第一个大于0的数,返回的下标是"+binarySearchFirstMore(0));
        System.err.println("找第一个大于8的数,返回的下标是"+binarySearchFirstMore(8));
        System.err.println("找第一个大于133的数,返回的下标是"+binarySearchFirstMore(133));
        System.err.println("---------------------------------");
        System.err.println("找第一个大于等于-11的数,返回的下标是"+binarySearchFirstMoreEquals(-11));
        System.err.println("找第一个大于等于0的数,返回的下标是"+binarySearchFirstMoreEquals(0));
        System.err.println("找第一个大于等于2的数,返回的下标是"+binarySearchFirstMoreEquals(2));
        System.err.println("找第一个大于等于9的数,返回的下标是"+binarySearchFirstMoreEquals(9));
        System.err.println("找第一个大于等于100的数,返回的下标是"+binarySearchFirstMoreEquals(100));
        System.err.println("---------------------------------");
        int l=Integer.MAX_VALUE-1000,r=Integer.MAX_VALUE;
        System.err.println("l="+l+" r="+r);
        System.err.println("溢出样例(l+r)/2   "+(l+r)/2);
        System.err.println("防止溢出l+(r-l)/2 "+(l+(r-l)/2));

    }


    //1.普通二分:查找数存不存在或者随便找一个
    public static int binarySearchOne(int target){
        int l=0,r=n-1,m;
        while(l<=r){
            m=(l+r)/2;
            if( a[m]<target ){
                l=m+1;
            }else if( a[m]>target ){
                r=m-1;
            }else
                return m;
        }
        return -1;
    }
    // 2.找最后一个小于target的数
    public static int binarySearchLastLess(int target){
        int l=0,r=n-1,m;
        while(l<=r){
            m=(l+r)/2;
            if( a[m]>=target )
                r=m-1;
            else
                l=m+1;
        }
        return r<0?-1:r;
    }
    // 3.找最后一个小于等于target的数
    public static int binarySearchLastLessEquals(int target){
        int l=0,r=n-1,m;
        while (l<=r){
            m=(l+r)/2;
            if( a[m]>target )
                r=m-1;
            else
                l=m+1;
        }
        return r<0?-1:r;
    }
    // 4.找第一个大于target的数
    public static int binarySearchFirstMore(int target){
        int l=0,r=n-1,m;
        while(l<=r){
            m=(l+r)/2;
            if( a[m]<=target )
                l=m+1;
            else
                r=m-1;
        }
        return l>=n?-1:l;
    }
    // 5.找第一个大于等于目标值的数
    public static int binarySearchFirstMoreEquals(int target){
        int l=0,r=n-1,m;
        while(l<=r){
            m=(l+r)/2;
            if( a[m]<target )
                l=m+1;
            else
                r=m-1;
        }
        return l>=n?-1:l;
    }
}

View Code

 

二、集合容器中的二分操作

1.有序不重复集合TreeSet

  • boolean contains(Object o) 判断是否存在元素o
  • E ceiling(E e) 返回第一个大于或等于e的元素
  • E higher(E e) 返回第一个严格大于e的元素
  • E floor(E e) 返回第一个小于或等于e的元素
  • E lower(E e) 返回第一个严格小于e的元素

如果以上方法没有找到元素,则返回null

无序不重复集合HashSet没有后四个方法

遍历集合

for(E e:treeSet)

2.有序不重复映射TreeMap

  • boolean contains(Object key) 判断是否存在键key
  • K ceilingKey(K key) 返回第一个大于或等于key的键
  • K higherKey(K key) 返回第一个严格大于key的键
  • K floorKey(K key) 返回第一个小于或等于key的键
  • K lowerKey(K key) 返回第一个严格小于key的键

如果以上方法没有找到元素,则返回null

无序不重复映射HashMap没有后四个方法

遍历集合

for (Map.Entry entry : treeMap.entrySet()) {
      System.out.println(entry);
}

 

 

 

三、推荐例题

二分查找的边界情况

 


程序员灯塔
转载请注明原文链接:二分查找的边界情况
喜欢 (0)