欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

如何写好一个二分搜索

程序员文章站 2024-03-20 17:49:46
...

如何写好一个二分搜索

最近写了一个二分搜索,结果不尽人意,总是出错。

所以翻了一些博客,看到一些关于使用循环不变体的方法来写二分搜索。

如何写出正确的二分搜索--https://www.cnblogs.com/wuyuegb2312/archive/2013/05/26/3090369.html 

我就写好一个二分搜索进行了一下总结:

步骤

  1. 确定你这个二分的目的,以下会举7个例子说一下常用的求解target;
  2. 确定条件,就三个,s[mid]>、==、<key时,left与right如何取值,确定之后有的可以合并;
  3. 确定循环的条件 while(left<=right),while(left<right),或者while(left<right-1),确定循环结束的条件,还要给出对不在循环的left、right的判断;

以下就手动举例编码对以上步骤进行实现。

1、搜索确定的key值

/**
     * target:搜索确定的key值
     *
     * 1. left<=right ----- 保证退出循环的时候,数组没数(left>right)里面的数为0,没找到就返回-1
     * 2. left=mid+1  ----- s[mid]<key 只可能在 [mid+1,right] 中
     * 3. right=mid-1  ---- s[mid]>key 只可能在 [left,mid-1] 中
     * 4. return mid ------ 找到就返回mid,找不到就返回-1
     * 5. 每次缩小的范围是right-mid+1 = ((right-left)>>1) +1 ,至少缩小一个
     * @param s
     * @param key
     * @return
     */
    public static int bs(int[] s,int key){
        int left=0;
        int right=s.length-1;
        int mid=0;
        while(left<=right){
            mid=left+((right-left)>>1);
            if(s[mid]>key){
                 right=mid-1;
            }
            else if(s[mid]<key){
                 left=mid+1;
            }
            else return mid;
        }
        return -1;
    }

2、搜索第一个出现的key值

/**
     * target:搜索第一个出现的key值(上一个方法搜到key之后就返回,可能是数组里的某一个)
     *
     * 1. left<right ----- 保证退出循环的时候,数组没数(left>right)里面的数为0,还没找到就返回-1
     *    || 或者里面的还有1个数(left=right),判断这个是否为key,返回left或者-1
     *
     *
     * 2. left=mid+1  ----- s[mid]<key 只可能在 [mid+1,right] 中
     *
     * 3. right=mid-1  ---- s[mid]>key 只可能在 [left,mid-1] 中
     *
     * 4. right = mid ------ s[mid]=key 可能在 [left,mid] 中,(有一种写法或者判断s[mid-1]是不是key,不是就直接返回mid,是就right=mid-1)
     *
     * 5. 每次缩小的范围是right-mid+1 = ((right-left)>>1) +1 ,至少缩小一个。
     *    || 或者是 right-mid =(right-left)>>1 可能不会缩小,如果判断条件是 right=left 或者 right=left+1 都不会缩小,会进入死循环。
     *      && 但是在 while(left<right) 的条件下为什么不考虑 right=left+1 导致死循环??
     *        && 因为出现该情况后,如果继续循环得到mid=left(***特殊所在),如果判断s[mid]==key 得到right=mid,那么需要再一次循环判断,此时left=right就退出循环了
     *          && 所以如果出现right=left+1也不会出现死循环。
     *
     * 6. 这里把s[mid]>key 和 s[mid]=key 的条件执行的结果合并为right= mid,因为 left<right 保证了
     * @param s
     * @param key
     * @return
     */
    public static int bsFirst(int[] s,int key){
        int left=0;
        int right=s.length-1;
        int mid=0;
        while(left < right){
            mid=left+((right-left)>>1);
            if(s[mid]<key){
                left=mid+1;
            }
            else {
                right=mid;
            }
        }
        if(s[left]==key){
            return left;
        }
        return -1;
    }

3、搜索最后一个出现的key值

 /**
     * target:搜索最后一个出现的key值(与上一个方法在while循环之处和结尾条件有些不同)
     *
     * 1. left<right-1 ----- 保证退出循环的时候,数组没数(left>right)里面的数为0,还没找到就返回-1
     *    ||或者里面的还有1个数(left=right),判断这个是否为key,返回left或者-1
     *    ||或者里面的还有2个数(left+1=right),判断这个left和right是否为key,返回left或者right或者-1
     *
     * 2. left=mid+1  ----- s[mid]<key 只可能在 [mid+1,right] 中
     *
     * 3. right=mid-1  ---- s[mid]>key 只可能在 [left,mid-1] 中
     *
     * 4. left = mid ------ s[mid]=key 可能在 [mid,right] 中,(思路:或者判断s[mid+1]是不是key,不是就直接返回mid,是就令left=mid+1;)
     *
     * 5. 每次缩小的范围是right-mid+1 = ((right-left)>>1) +1 ,至少缩小一个。
     *    ||或者是 mid-left =(right-left)>>1 可能不会缩小,如果判断条件是 right=left 或者 right=left+1 都不会缩小,会进入死循环。
     *       && 但是此时为什么在 while(left<right) 的条件下要考虑 right=left+1 导致死循环??
     *            && 因为出现该情况后,如果继续循环得到mid=left(***特殊所在),如果判断s[mid]==key 得到left=mid,那么需要再一次循环判断,依旧满足 left<right
     *              && 这样就会出现死循环。所以采用while(left+1<right) 的条件。
     *
     * 6. 这里把s[mid]>key 和 s[mid]=key 的条件执行的结果合并为right= mid,因为 left<right 保证了
     * @param s
     * @param key
     * @return
     */
    public static int bsLast(int[] s,int key){
        int left=0;
        int right=s.length-1;
        int mid=0;
        while(left+1 < right){
            mid=left+((right-left)>>1);
            if(s[mid]>key){
                right=mid-1;
            }
            else {
                left=mid;
            }
        }
        if(s[right]==key){
            return right;
        }
        if(s[left]==key){
            return left;
        }
        return -1;
    }

4、搜索最近大于key的值

/**
     * target:搜索最近大于key的值
     *
     * 1. left<right-1 ----- 保证退出循环的时候,数组没数(left>right)里面的数为0,还没找到就返回-1
     *    ||或者里面的还有1个数(left=right),判断这个是否为key,返回left或者-1
     *    ||或者里面的还有2个数(left+1=right),判断这个left和right是否为key,返回left或者right或者-1
     *
     * 2. left=mid+1  ----- s[mid]<key 只可能在 [mid+1,right] 中
     *
     * 3. right=mid  ---- s[mid]>key 只可能在 [left,mid] 中(mid有可能是最近大于key的下标)(思路:或者判断s[mid-1]是不是大于key,不是就直接返回mid,是就令right=mid-1;)
     *
     * 4. left = mid+1 ------ s[mid]=key 可能在 [mid+1,right] 中
     *
     * 5. 每次缩小的范围是right-mid+1 = ((right-left)>>1) +1 ,至少缩小一个。
     *    ||或者是 right-mid =(right-left)>>1 可能不会缩小,如果判断条件是 right=left 或者 right=left+1 都不会缩小,会进入死循环。
     *       && 但是此时为什么在 while(left<right) 的条件下不考虑 right=left+1 导致死循环??
     *            && 因为出现该情况后,如果继续循环得到mid=left(***特殊所在),如果判断s[mid]>key 得到right=mid,那么需要再一次循环判断,不满足 left<right
     *              && 这样就不会出现死循环。所以采用while(left<right) 的条件。
     *
     * @param s
     * @param key
     * @return
     */
    public static int bsFirstMoreThan(int[] s,int key){
        int left=0;
        int right=s.length-1;
        int mid=0;
        while(left<right){
            mid=left+((right-left)>>1);
            if(s[mid]>key){
                right=mid;
            }
            else{
                left=mid+1;
            }
        }
        if(s[left]>key){
            return left;
        }
        return -1;
    }

5、搜索最近小于key的值

 /**
     *  target:搜索最近小于key的值
     *  经过以上4个例子理解,mid=left+((right-left)>>1)的特殊性,就可以直接写出下面代码。
     * @param s
     * @param key
     * @return
     */
    public static int bsFirstLessThan(int[] s,int key){
        int left=0;
        int right=s.length-1;
        int mid=0;
        while (left < right - 1) {
            mid=left+((right-left)>>1);
            if(s[mid]>=key){
                right=mid-1;
            }
            else{
                left=mid;
            }
        }
        if(s[right]<key){
            return right;
        }
        if(s[left]<key){
            return left;
        }
        return -1;
    }

6、搜索小于等于key的第一个数位置

/**
     * target:小于等于key的第一个数位置
     * 可以先找到最近大于key的数的位置,再取前一位。
     *
     * @param s
     * @param key
     * @return
     */
    public static int  bsFirstLessThanOrEqual(int[] s,int key){
        int index=bsFirstMoreThan(s,key);
        if(index<=0){
            return -1;
        }
        return index-1;
    }

7、搜索大于等于key的第一个数位置

/**
     * target:大于等于key的第一个数位置,
     * 可以先找到最近小于key的数的位置,再取后一位。
     *
     * @param s
     * @param key
     * @return
     */
    public static int  bsFirstMoreThanOrEqual(int[] s,int key){
        int index=bsFirstLessThan(s,key);
        if(index<0||index==s.length-1){
            return -1;
        }
        return index+1;
    }

测试与结果

 public static void main(String[] args) {
        int [] s={0,1,2,2,2,2,2,3,4};
        System.out.println("存在数");
        System.out.println(BinarySearch.bsFirst(s, 2));
        System.out.println(BinarySearch.bsLast(s, 2));
        System.out.println(BinarySearch.bsFirstMoreThan(s, 2));
        System.out.println(BinarySearch.bsFirstLessThan(s, 2));
        System.out.println(BinarySearch.bsFirstLessThanOrEqual(s, 2));
        System.out.println(BinarySearch.bsFirstMoreThanOrEqual(s, 2));

        int [] s1={0,1,3,4};
        System.out.println("不存在数");
        System.out.println(BinarySearch.bsFirst(s1, 2));
        System.out.println(BinarySearch.bsLast(s1, 2));
        System.out.println(BinarySearch.bsFirstMoreThan(s1, 2));
        System.out.println(BinarySearch.bsFirstLessThan(s1, 2));
        System.out.println(BinarySearch.bsFirstLessThanOrEqual(s1, 2));
        System.out.println(BinarySearch.bsFirstMoreThanOrEqual(s1, 2));
    }
存在数
2
6
7
1
6
2
不存在数
-1
-1
2
1
1
2

总结

想要快速的写出二分搜索

  1. 明确三个条件;
  2. mid=left+((right-left)>>1)的特殊性;
  3. 掌握基本的编写结构,快速上手;