面试官：说说你对二分查找的理解？如何实现？应用场景？

本文转载自微信公众号「JS每日一题」，作者灰灰。转载本文请联系JS每日一题众号。

网站设计、网站制作,成都做网站公司-创新互联已向上千多家企业提供了,网站设计,网站制作,网络营销等服务!设计与技术结合,多年网站推广经验,合理的价格为您打造企业品质网站。

一、是什么

在计算机科学中，二分查找算法，也称折半搜索算法，是一种在有序数组中查找某一特定元素的搜索算法

想要应用二分查找法，则这一堆数应有如下特性：

  • 存储在数组中
  • 有序排序

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束

如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较

如果在某一步骤数组为空，则代表找不到

这种搜索算法每一次比较都使搜索范围缩小一半

如下图所示：

相比普通的顺序查找，除了数据量很少的情况下，二分查找会比顺序查找更快，区别如下所示：

二、如何实现

基于二分查找的实现，如果数据是有序的，并且不存在重复项，实现代码如下：

 
 
 
 
    
  
  
  
  
  1. function BinarySearch(arr, target) { 
    2.   
  
  
  
  2.     if (arr.length <= 1) return -1 
    3.   
  
  
  
  3.     // 低位下标 
    4.   
  
  
  
  4.     let lowIndex = 0 
    5.   
  
  
  
  5.     // 高位下标 
    6.   
  
  
  
  6.     let highIndex = arr.length - 1 
    7.   
  
  
  
  7.  
    8.   
  
  
  
  8.     while (lowIndex <= highIndex) { 
    9.   
  
  
  
  9.         // 中间下标 
    10.   
  
  
  
  10.         const midIndex = Math.floor((lowIndex + highIndex) / 2) 
    11.   
  
  
  
  11.         if (target < arr[midIndex]) { 
    12.   
  
  
  
  12.             highIndex = midIndex - 1 
    13.   
  
  
  
  13.         } else if (target > arr[midIndex]) { 
    14.   
  
  
  
  14.             lowIndex = midIndex + 1 
    15.   
  
  
  
  15.         } else { 
    16.   
  
  
  
  16.             // target === arr[midIndex] 
    17.   
  
  
  
  17.             return midIndex 
    18.   
  
  
  
  18.         } 
    19.   
  
  
  
  19.     } 
    20.   
  
  
  
  20.     return -1 
    21.   
  
  
  
  21. } 
    22.

如果数组中存在重复项，而我们需要找出第一个制定的值，实现则如下：

 
 
 
 
    
  
  
  
  
  1. function BinarySearchFirst(arr, target) { 
    2.   
  
  
  
  2.     if (arr.length <= 1) return -1 
    3.   
  
  
  
  3.     // 低位下标 
    4.   
  
  
  
  4.     let lowIndex = 0 
    5.   
  
  
  
  5.     // 高位下标 
    6.   
  
  
  
  6.     let highIndex = arr.length - 1 
    7.   
  
  
  
  7.  
    8.   
  
  
  
  8.     while (lowIndex <= highIndex) { 
    9.   
  
  
  
  9.         // 中间下标 
    10.   
  
  
  
  10.         const midIndex = Math.floor((lowIndex + highIndex) / 2) 
    11.   
  
  
  
  11.         if (target < arr[midIndex]) { 
    12.   
  
  
  
  12.             highIndex = midIndex - 1 
    13.   
  
  
  
  13.         } else if (target > arr[midIndex]) { 
    14.   
  
  
  
  14.             lowIndex = midIndex + 1 
    15.   
  
  
  
  15.         } else { 
    16.   
  
  
  
  16.             // 当 target 与 arr[midIndex] 相等的时候，如果 midIndex 为0或者前一个数比 target 小那么就找到了第一个等于给定值的元素，直接返回 
    17.   
  
  
  
  17.             if (midIndex === 0 || arr[midIndex - 1] < target) return midIndex 
    18.   
  
  
  
  18.             // 否则高位下标为中间下标减1，继续查找 
    19.   
  
  
  
  19.             highIndex = midIndex - 1 
    20.   
  
  
  
  20.         } 
    21.   
  
  
  
  21.     } 
    22.   
  
  
  
  22.     return -1 
    23.   
  
  
  
  23. } 
    24.

实际上，除了有序的数组可以使用，还有一种特殊的数组可以应用，那就是轮转后的有序数组

有序数组即一个有序数字以某一个数为轴，将其之前的所有数都轮转到数组的末尾所得

例如，[4, 5, 6, 7, 0, 1, 2]就是一个轮转后的有序数组

该数组的特性是存在一个分界点用来分界两个有序数组，如下：

分界点有如下特性：

  • 分界点元素 >= 第一个元素
  • 分界点元素 < 第一个元素

代码实现如下：

 
 
 
 
    
  
  
  
  
  1. function search (nums, target) { 
    2.   
  
  
  
  2.   // 如果为空或者是空数组的情况 
    3.   
  
  
  
  3.   if (nums == null || !nums.length) { 
    4.   
  
  
  
  4.     return -1; 
    5.   
  
  
  
  5.   } 
    6.   
  
  
  
  6.   // 搜索区间是前闭后闭 
    7.   
  
  
  
  7.   let begin = 0, 
    8.   
  
  
  
  8.     end = nums.length - 1; 
    9.   
  
  
  
  9.   while (begin <= end) { 
    10.   
  
  
  
  10.     // 下面这样写是考虑大数情况下避免溢出 
    11.   
  
  
  
  11.     let mid = begin + ((end - begin) >> 1); 
    12.   
  
  
  
  12.     if (nums[mid] == target) { 
    13.   
  
  
  
  13.       return mid; 
    14.   
  
  
  
  14.     } 
    15.   
  
  
  
  15.     // 如果左边是有序的 
    16.   
  
  
  
  16.     if (nums[begin] <= nums[mid]) { 
    17.   
  
  
  
  17.       //同时target在[ nums[begin],nums[mid] ]中，那么就在这段有序区间查找 
    18.   
  
  
  
  18.       if (nums[begin] <= target && target <= nums[mid]) { 
    19.   
  
  
  
  19.         end = mid - 1; 
    20.   
  
  
  
  20.       } else { 
    21.   
  
  
  
  21.         //否则去反方向查找 
    22.   
  
  
  
  22.         begin = mid + 1; 
    23.   
  
  
  
  23.       } 
    24.   
  
  
  
  24.       //如果右侧是有序的 
    25.   
  
  
  
  25.     } else { 
    26.   
  
  
  
  26.       //同时target在[ nums[mid],nums[end] ]中，那么就在这段有序区间查找 
    27.   
  
  
  
  27.       if (nums[mid] <= target && target <= nums[end]) { 
    28.   
  
  
  
  28.         begin = mid + 1; 
    29.   
  
  
  
  29.       } else { 
    30.   
  
  
  
  30.         end = mid - 1; 
    31.   
  
  
  
  31.       } 
    32.   
  
  
  
  32.     } 
    33.   
  
  
  
  33.   } 
    34.   
  
  
  
  34.   return -1; 
    35.   
  
  
  
  35. }; 
    36.

对比普通的二分查找法，为了确定目标数会落在二分后的哪个部分，我们需要更多的判定条件

三、应用场景

二分查找法的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%AC

https://www.cnblogs.com/ider/archive/2012/04/01/binary_search.html

网页题目：面试官：说说你对二分查找的理解？如何实现？应用场景？
浏览路径：http://www.stwzsj.com/qtweb/news47/1247.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

云服务器知识

各行业网站

移动手机网站制作　　 　成都电信服务器托管　　 　广安搬家公司　　 　兴宏源活动板房　　 　网站推广公司　　 　域名注册　　 　成都手机网站建设　　 　品牌网站建设　　 　绵阳科技城电信IDC机房　　 　成都小程序开发　　 　软文发稿　　 　复盛机电设备　　 　内江服务器托管　　 　仿古建筑设计　　 　手机网站制作　　 　微信营销　　 　广告媒介投放　　 　重庆网站制作　　 　手机网站建设公司　　 　成都小程序开发公司