二分查找的四种变型

原创
2021/12/30 12:00
阅读数 62
package huawei;

public class BinarySearch {

    // 查找第一个值等于给定值的元素
    public int bsearch(int[] a, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] > value) {
                high = mid - 1;
            } else if (a[mid] < value) {
                low = mid + 1;
            } else {
                // 如果mid等于0,那这个元素已经是数组的第一个元素,那它肯定是我们要找的
                // 如果mid不等于0,但a[mid]的前一个元素a[mid-1]不等于value,那也说明a[mid]就是我们要找的第一个值等于给定值的元素
                // 如果经过检查之后发现a[mid]前面的一个元素a[mid-1]也等于value,那说明此时的a[mid]肯定不是我们要查找的第一个值等于给定值的元素。
                // 那我们就更新high=mid-1,因为要找的元素肯定出现在[low, mid-1]之间。
                if ((mid == 0) || (a[mid-1] != value)) {
                    return mid;
                }
                else {
                    high = mid - 1;
                }
            }
        }
        return -1;
    }

    // 查找最后一个值等于给定值的元素
    public int bsearch2(int[] a, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] > value) {
                high = mid - 1;
            } else if (a[mid] < value) {
                low = mid + 1;
            } else {
                // 如果mid等于n-1,那这个元素是数组的最后一个元素,那它肯定是我们要找的
                // 如果mid不等于n-1,但a[mid]的前一个元素a[mid+1]不等于value,那也说明a[mid]就是我们要找的最后一个值等于给定值的元素
                // 如果经过检查之后发现a[mid]后面的一个元素a[mid+1]也等于value,那说明此时的a[mid]肯定不是我们要查找的最后一个值等于给定值的元素。
                // 那我们就更新low=mid+1,因为要找的元素肯定出现在[mid+1, high]之间。
                if ((mid == n-1) || (a[mid+1] != value)) {
                    return mid;
                }
                else {
                    low = mid + 1;
                }
            }
        }
        return -1;
    }

    // 查找第一个大于等于给定值的元素(给定的值可能不存在)
    public int bsearch3(int[] a, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] >= value) {
                // 对于a[mid]大于等于给定值value的情况,我要看一下这个值是否是数组的第一个元素或者是否它前一个值小于value,如果符合则a[mid]就是要找的第一个大于等于给定值的元素
                // 如果a[mid-1]不小于value,说明要找的元素还在当前mid的前面,所以区间变为为[low, mid-1]
                if ((mid == 0) || (a[mid-1] < value)) {
                    return mid;
                } else {
                    high = mid - 1;
                }
            } else {
                // 如果小于value范围肯定要缩小为[mid+1, high]
                low = mid + 1;
            }
        }
        return -1;
    }

    // 查找最后一个小于等于给定值的元素(给定的值可能不存在)
    public int bsearch4(int[] a, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] <= value) {
                // 对于a[mid]大于等于给定值value的情况,我要看一下这个值是否是数组的最后一个元素或者是否它后一个值大于value,如果符合则a[mid]就是要找的最后一个小于等于给定值的元素
                // 如果a[mid+1]小于等于value,说明要找的元素还在当前mid的后面,所以区间变为为[mid+1, high]
                if ((mid == n-1) || (a[mid+1] > value)) {
                    return mid;
                } else {
                    low = mid + 1;
                }
            } else {
                // 如果大于value范围肯定要缩小为[low, mid-1]
                high = mid - 1;
            }
        }
        return -1;
    }

}

这里直接贴代码了,感谢王争大大的精彩讲解了。

循环有序数组的二分查找

    // 循环有序数组的查找,如:4,5,6,7,1,2,3
    // 有一个性质:以数组中间点为分区,会将数组分成一个有序数组和一个循环有序数组。
    // 如果首元素小于mid,说明前半部分是有序的,后半部分是循环有序数组
    // 如果首元素大于mid,说明后半部分是有序的,前半部分是循环有序的数组;
    // 如果目标元素在有序数组范围中,使用二分查找; 如果目标元素在循环有序数组中,设定数组边界后,使用以上方法继续查找。
    // 时间复杂度为O(logN)
    public int bsearch5(int[] a, int n, int value) {
        int low = 0;
        int high = n - 1;
        int mid = low + (high - low)/2;
        while (low <= high) {
            if (a[mid] == value) {
                return mid;
            }

            if (a[low] <= a[mid]) {  //前半部分是升序的,使用二分查找
                if (value >= a[low] && value <= a[mid]) { // 在左边范围内
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            } else {  // 后半部分是升序的,使用二分查找
                if (value >= a[mid] && value <= a[high]) {  // 在右边范围内
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            mid = low + (high - low)/2;
        }
        return -1; // 没有找到
    }

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部