”二分查找“算法的时间复杂度
source link: https://itimetraveler.github.io/2016/04/06/%E2%80%9D%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE%E2%80%9C%E7%AE%97%E6%B3%95%E7%9A%84%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
”二分查找“算法的时间复杂度
算法的时间复杂度无非就是for、while等包含起来的基本运算单元的循环次数
1、二分查找
二分查找（binary search），也称作折半查找（half-interval search），每次划分一半进行下一步搜索，所以时间复杂度无非就是while循环的次数！
//二分查找 Java 实现
public static int binarySearch(Integer[] srcArray, int des) {
int low = 0;
int high = srcArray.length - 1;
while ((low <= high) && (low <= srcArray.length - 1)
&& (high <= srcArray.length - 1)) {
int middle = (high + low) >> 1;
if (des == srcArray[middle]) {
return middle;
} else if (des < srcArray[middle]) {
high = middle - 1;
} else {
low = middle + 1;
}
}
return -1;
}
2、时间复杂度
比如：总共有n个元素，每次查找的区间大小就是n，n/2，n/4，…，n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数。
由于n/2^k取整后>=1，即令n/2^k=1，
可得k=log2n,（是以2为底，n的对数），所以时间复杂度可以表示O()=O(logn)
Recommend
-
47
二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。所以在采用二分法查找时，数据需是有序不重复的，如果是无序的也可通过选择排序、冒泡排序等数组排序方法进行排序之后，就可以使用二分法查找。 基本...
-
52
二分查找是搜索算法中的一种，用来搜索 有序数组 二分查找：...
-
10
如何运用二分查找算法 👆让天下没有难刷的算法！若 GitBook 访问太慢，可尝试
-
7
你是那10%可以实现二分查找算法的程序员吗？ 浏览:5918次 出处信息 原文链接：
-
12
Mr.Feng BlogNLP、深度学习、机器学习、Python、Go经典的二分查找算法体会下经典的二分查找算法。二分操作算法只能由于有序数组，时间复杂度是O(lgN)。在链表情况...
-
11
这里总结了一些前端常见的算法。1、排序问题1.1冒泡排序该算法就是依次比较大小，小的的大的进行位置上的交换。var ex=[8,95,34,21,53,12];
-
8
一文搞懂二分查找算法！-51CTO.COM 一文搞懂二分查找算法！ 作者：月伴飞鱼 2022-03-28 10:03:58 从定义可知，运用二分搜索的前提是数组必须是排好序的，另外，输入并不一定是数组，也有可能是给...
-
4
LC T668笔记 & 有关二分查找、第K小数、BFPRT算法 LC T668笔记 【...
-
3
基本算法篇——二分查找 本次我们介绍基础算法中的二分查找，我们会从下面几个角度来介绍二分查找： 二分查找简述 二分查找模板 二分查找边界 例题数的范围
-
3
前端算法之二分查找 - coder__wang - 博客园 文*弱*书*生 脚踏实地行，海阔天空飞
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK