二分查找变种

该算法有很多版本,这里给出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);    // 参照官方文档自定义值
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【模板小程序】翻转一个句子中的单词

    xiaoxi666
  • 【左神算法课】子数组最大差值小于某阈值,求满足条件的子数组个数

      1.从第一个元素开始依次向后遍历,同时维护两个窗口(由于要同时操作窗口的头部和尾部,故采用双端队列):

    xiaoxi666
  • 【模板小程序】二分法插入排序

    Java版源程序来自:http://www.cnblogs.com/PerkinsZhu/p/5674572.html,在此感谢。

    xiaoxi666
  • Ubuntu 安装 tensorflow-gpu 1.4 +CUDA 8.0 +cuDNN详细教程

    磐创AI
  • 简谈快速排序

    Jacklin
  • [PHP]引用返回与节省内存

    PHP中的引用是什么: 1.在 PHP 中引用意味着用不同的名字访问同一个变量内容 2.引用可以被看作是 Unix 文件系统中的硬链接。

    陶士涵
  • iBaits.Net(1):简介与安装

    iBATIS提供的持久层框架包括SQL Maps和Data Access Objects(DAO),同时还提供一个利用这个框架开发的JPetStore实例。 ...

    小白哥哥
  • 几个Java数组的谜题

    Jerry Wang
  • 【AlexeyAB DarkNet框架解析】九,YOLOV3损失函数代码详解(yolo_layer.c)

    前面已经讲完了YOLOV1/V2的损失函数代码解析,今天为大家带来YOLOv3的损失函数解析。YOLOV3的损失函数在YOLOV2的基础上,用多个独立的逻辑回归...

    BBuf
  • linux nginx服务器域名泛解析配置

    要配置泛解析域名就需要先到网站所在的DNS服务商处设置A记录。 列如要解析www.liezi.net,请在主机记录(RR)处填写www 常见命名前缀...

    葫芦

扫码关注云+社区

领取腾讯云代金券