首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >二分查找变种

二分查找变种

作者头像
xiaoxi666
发布2018-10-29 17:24:10
3410
发布2018-10-29 17:24:10
举报
文章被收录于专栏:xiaoxi666的专栏xiaoxi666的专栏

该算法有很多版本,这里给出java中实现比较好的一种方式。其中,>>>为无符号右移。

二分查找第一个值为obj的元素

/**
 * 二分查找第一个值为obj的元素
 * @param array
 * @param obj
 * @return 若数组为空,返回-1; 若查找到,则返回其索引; 若未查找到,返回负值(可能为-1)
 */
public static int binarySearchFirstEqual (int[] array, int obj) {
    if (array == null || array.length == 0) {
        return -1;
    }
    int left = 0;
    int right = array.length - 1;
    while (left < right) {
        int mid = left + ((right - left) >>> 1);
        if (array[mid] < obj) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    if (array[left] == obj) {
        return left;
    }
    return -(left + 1);    // 参照官方文档自定义值
}

二分查找最后一个值为obj的元素

/**
 * 二分查找最后一个值为obj的元素
 * @param array
 * @param obj
 * @return 若数组为空,返回-1; 若查找到,则返回其索引; 若未查找到,返回负值(可能为-1)
 */
public static int binarySearchLastEqual (int[] array, int obj) {
    if (array == null || array.length == 0) {
        return -1;
    }
    int left = 0;
    int right = array.length - 1;
    while (left <= right) {
        int mid = left + ((right - left) >>> 1);
        if (array[mid] <= obj) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    if (right >= 0 && array[right] == obj) {
        return right;
    }
    return -(right + 1);    // 参照官方文档自定义值
}

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018-09-27 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 二分查找第一个值为obj的元素
  • 二分查找最后一个值为obj的元素
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档