二分查找

栏目: 编程工具 · 发布时间: 6年前

内容简介:$O(logN)$令 $C(N)$ 为在大小为 $N$ 的数组中查找一个键所需进行的比较次数。显然有 $C(0) = 0$ 、$C(1)=1$
  • 在数组有序的前提下
  • 先将被查找的键和子数组的中间键比较,如果被查找的键小于中间键,就在左子数组查找,大于就在右子数组查找,否则中间键就是要找的键
  • 若表中存在该键,则返回该键的位置
  • 否则返回小于该键的元素数量

时间复杂度

$O(logN)$

分析

令 $C(N)$ 为在大小为 $N$ 的数组中查找一个键所需进行的比较次数。

显然有 $C(0) = 0$ 、$C(1)=1$

对于 $N>0$ 可得到归纳关系式:

$C(N)\leq C(\lfloor N/2 \rfloor)+1$

无论查找会在中间元素的左侧还是右侧继续,子数组大小都不会超过 $\lfloor N/2 \rfloor$ ,需要一次比较来检查中间元素和被查找的键是否相等,并决定继续查找左子数组还是右子数组。

当 $N=2^n-1$ 时,$\lfloor N/2 \rfloor=2^{n-1}+1$ ,

迭代得:

$C(2^n-1)\leq C(2^0)+n$

得:$C(N)=C(2^n)\leq n+1<lgN+1$

图示

二分查找

代码

非递归

public static int binarySearch (int[] integer, int n, int key) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (key < integer[mid]) {
                high = mid - 1;
            }
            else if (key > integer[mid]){
                low = mid + 1;
            }
            else {
                return mid; //查找到
            }
        }
        return low;  //未查找到,返回比其少的元素数量
    }

递归

public static int search (int[] integer, int key) {
        int lo = 0, hi = integer.length - 1;
        return binarySearch(integer, key, lo, hi);
    }

public static int binarySearch (int[] integer,  int key, int lo, int hi) {
        if (lo > hi)
            return lo;    //未查找到,返回比其少的元素数量
        int mid = (lo + hi) / 2;
        if (integer[mid] == key)
            return mid;
        else if (integer[mid] > key)
            return binarySearch(integer, key, 0, mid - 1);
        else
            return binarySearch(integer, key, mid + 1, hi);
    }

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

ODPS权威指南

ODPS权威指南

李妹芳 / 人民邮电出版社 / 2014-12 / 69元

ODPS(Open Data Processing Service)是阿里巴巴自主研发的海量数据处理和分析的服务平台,主要应用于数据分析、海量数据统计、数据挖掘、机器学习和商业智能等领域。目前,ODPS不仅在阿里内部得到广泛应用,享有很好的口碑,正逐步走向第三方开放市场。 本书是学习和掌握ODPS的权威指南,作者来自阿里ODPS团队。全书共13章,主要内容包括:ODPS入门、整体架构、数据通......一起来看看 《ODPS权威指南》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

SHA 加密
SHA 加密

SHA 加密工具

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具