二分法查找元素二分法查找

二分法查找介绍二分法查找是什么1、算法：二分法查找适用于数据量较大时，但是数据需要先排好顺序。
2、主要思想是：（设查找的数组区间为array[low, high]）确定该区间的中间位置K 。将查找的值T与array[k]比较。若相等，查找成功返回此位置；否则确定新的查找区域，继续二分查找。区域确定如下：a.array[k]T 由数组的有序性可知array[k,k+1,……,high]T;故新的区间为array[low,……，K-1]b.array[k]t p="" 类似上面查找区间为array[k+1,……，high] 。每一次查找与中间值比较，可以确定是否查找成功，不成功当前查找区间将缩小一半，递归查找即可。时间复杂度为:o(log2n) 。
excel中LOOKUP函数的二分法查找策略excel中LOOKUP函数的二分法查找策略
二分法查找又称折半查找，它是一种效率较高的查找算法。二分法通常要求目标数组中的数据是有序排列的。LOOKUP函数所使用的查找策略就是二分法，不仅仅是LOOKUP，其实VLOOKUP/HLOOKUP函数在其第四参数为True时、MATCH函数在其第三参数为1时也都是遵循了二分法的'查找原则来进行运算的。
二分法的具体方法，通常会通过下面这个流程图来表达：
但流程图过于抽象，为了让这个查找过程更容易理解，尝试使用其他方法再进行一些解读。
首先是算法文字描述：
【二分法查找元素二分法查找】1, 将查找值与目标向量中的“中位值”进行对比
2, 大于中位值时，以中位作为边界，继续在其右侧取新的中位值继续对比
3, 小于中位值时，以中位作为边界，继续在其左侧取新的中位值继续对比
4, 等于中位值时，依次判断其右侧数值是否继续相等，直到不相等时返回最后一个相等的数值
5, 当中位位置与边界重叠时，中止对比，此时如果查找值大于中位值，则返回中位值;如果查找值小于中位值，则返回中位左侧数值。如果左侧数值不存在，返回#N/A
注：上面提到的“中位值”指的是目标数组中位置居中的数据(数据个数为偶数时，中位等于个数除以2;数据个数为奇数时，中位等于个数+1除以2)，与统计学上传统意义上的中位值不完全相同
再配合下面两张运算过程图加深理解：
最后，再提供一个自动演示查找运算过程的Excel文档：;
js实现二分法查找方法所谓二分法查找法，也就是折半查找，它是一种在有序数组查找特定元素的搜索算法。
参考《前端程序员面试秘籍》
思想：从数组中开始查找，如果该元素是要搜索的目标元素，则循环结束，如果不是继续下一步，如果目标元素大于或者小于中间元素，则在数组大于或者小于中间元素的那一半区域进行查找，进而重复上面操作。如果数组是空的，则找不到该目标元素。

文章插图

二分法查找元素 二分法查找

秒懂生活扩展阅读

二分法查找元素二分法查找