data_structure_and_algorithm -- 4种常见二分查找变形问题

跟大神学习进步还是很快的,再说的直接一点就是:花钱买时间呃

二分查找变形问题:

(1)查找第一个值等于给定值的元素

(2)查找最后一个值等于给定值的元素

(3)查找第一个大于等于给定值的元素

(4)查找最后一个小于等于给定值的元素

//(1)查找第一个值等于给定值的元素
public int bsearch1(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{
            if ((mid == 0) || (a[mid-1] != value)) return mid;
            else high = mid - 1;
        }
    }
    return -1;
}

//(2)查找最后一个值等于给定值的元素
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{
            if ((mid == n-1) || (a[mid+1] != value)) return mid;
            else low = mid + 1;
        }
    }
    return -1;
}

//(3)查找第一个大于等于给定值的元素
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){
            if ((mid==0 || a[mid-1] < value)) return mid;
            else high = mid - 1;
        }else{
            low = mid + 1
        }
    }
    return -1;
}

//(4)查找最后一个小于等于给定值的元素
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){
            high = mid - 1; 
        }else {
            if ((mid==n-1 || a[mid+1] > value)) return mid;
            else low = mid + 1;
        }
    }
    return -1;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券