内容简介:$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); }
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Web渗透技术及实战案例解析
陈小兵 / 范渊、孙立伟 / 电子工业出版社 / 2012-4 / 89.00元
《Web渗透技术及实战案例解析》从Web渗透的专业角度,结合网络安全中的实际案例,图文并茂地再现Web渗透的精彩过程。《Web渗透技术及实战案例解析》共分7章,由浅入深地介绍和分析了目前网络流行的Web渗透攻击方法和手段,并结合作者多年的网络安全实践经验给出了相对应的安全防范措施,对一些经典案例还给出了经验总结和技巧,通过阅读《Web渗透技术及实战案例解析》可以快速掌握目前Web渗透的主流技术。《......一起来看看 《Web渗透技术及实战案例解析》 这本书的介绍吧!