本文转载自微信公众号《JS日报》，作者灰灰。转载本文请联系JS每日问号。1.什么是计算机科学中的二分查找算法，又称二分查找算法，是一种在有序数组中查找特定元素的查找算法如果要应用二分查找方法，那堆数字应该具有以下特点：存储在一个有序排序的数组中。搜索过程从数组的中间元素开始。如果中间元素恰好是要查找的元素，查找过程结束。如果特定元素大于或小于中间元素，则搜索一半元素，并从中间元素开始比较。如果在某一步数组为空，则表示找不到该搜索算法。每次比较将查找范围缩小一半，如下图所示：与普通顺序查找相比，除了数据量少之外，二分查找会比顺序查找快，区别如下：2.如何实现基于二分查找的实现，如果数据是有序的，没有重复的，实现代码如下：functionBinarySearch(arr,target){if(arr.length<=1)return-1//lowsubscriptletlowIndex=0//高下标lethighIndex=arr.length-1while(lowIndex<=highIndex){//中下标constmidIndex=Math.floor((lowIndex+highIndex)/2)if(targetarr[midIndex]){lowIndex=midIndex+1}else{//target===arr[midIndex]returnmidIndex}}return-1}如果数组中有重复项，我们需要找到第一个指定值，实现如下：functionBinarySearchFirst(arr,target){if(arr.length<=1)return-1//lowsubscriptletlowIndex=0//highsubscriptlethighIndex=arr.length-1while(lowIndex<=highIndex){//中间下标constmidIndex=Math.floor((lowIndex+highIndex)/2)if(target;arr[midIndex]){lowIndex=midIndex+1}else{//当target等于arr[midIndex]时，如果midIndex为0或者前一个数小于target，则第一个等于给定值的为找到元素，直接返回if(midIndex===0||arr[midIndex-1]=首元素分界点元素<首元素代码实现为functionsearch(nums,target){//如果为空或者空数组if(nums==null||!nums.length){return-1;}//letbegin=前后关闭搜索区间0,end=nums.length-1;while(begin<=end){//下面写的是考虑大数避免溢出letmid=begin+((end-begin)>>1);if(nums[mid]==target){returnmid;}//如果左边是有序的if(nums[begin]<=nums[mid]){//同时target在[nums[begin],nums[mid]],然后在这个有序区间内查找if(nums[begin]<=target&&target<=nums[mid]){end=mid-1;}else{//否则往反方向查找begin=mid+1;}//如果右边是有序的}else{//同时target在[nums[mid],nums[end]],则searchif(nums[mid]<=target&&target<=nums[end]){begin=mid+1;}else{end=mid-1;}}}return-1;};与普通的二分查找法相比，为了判断目标数的哪一部分会落在二分之后，我们需要morejudgments条件三、应用场景二分查找方式的O(logn)使得它成为一个非常高效的算法，但是它的缺陷也很明显，就在它的局限之上：有序：我们很难保证我们的数组都是顺序数组：数组读取的效率是O(1)，但是插入和删除一个元素的效率是O(n)，而且数组的存储需要连续的内存空间，不适合大数据。关于二分查找的应用场景主要有：不适合数据量太小的数组；如果数组太小，直接顺序遍历可能会更快更容易当它占据了整个遍历算法的大部分时间时，那么使用二分查找可以有效减少元素比较的次数。它不适用于数据过多的数组。二分查找使用的数据结构是一个序列表，也就是一个数组，数组需要是连续的。对于内存空间，系统不一定有这么大的连续内存空间可以参考https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%90%9C%E5%B0%8B%E6%BC%94%E7%AE%97%E6%B3%95#javascript_%E7%89%88%E6%9C%AChttps://www.cnblogs.com/ider/存档/2012/04/01/binary_search.html
