编辑
2023-11-23
数据结构与算法
00
请注意,本文编写于 92 天前,最后修改于 92 天前,其中某些信息可能已经过时。

目录

什么是二分查找
如何实现二分查找
二分查找的实现原理
总结

最近在面试的时候被问到手写实现二分查找,虽然二分查找很早就听过,也知道实现原理,但是手撸起来,总是差点意思,正好复习一下。作为前端程序员,可能面试绝大部分公司不需要能写很复杂的算法问题,但是这些基本的数据结构和常见算法,还是得能手撸出来。

什么是二分查找

二分查找是一种在有序数组中查找目标元素的算法,它的基本思想是每次比较数组的中间元素和目标元素,如果相等则返回中间元素的索引,如果不相等则根据比较结果缩小查找范围,直到找到目标元素或者查找范围为空。二分查找的时间复杂度是O(log n),其中n是数组的长度,它比顺序查找的时间复杂度O(n)要快得多。

如何实现二分查找

下面是用js语言实现二分查找的代码示例,其中arr是有序数组,target是要查找的元素,函数返回target在arr中的索引,如果不存在则返回-1。

js
// 定义二分查找函数 function binarySearch(arr, target) { // 定义查找范围的左右边界 let left = 0; let right = arr.length - 1; // 当左边界小于等于右边界时,继续查找 while (left <= right) { // 计算中间元素的索引 let mid = Math.floor((left + right) / 2); // 如果中间元素等于目标元素,返回索引 if (arr[mid] === target) { return mid; } // 如果中间元素小于目标元素,说明目标元素在右半部分,将左边界移动到中间元素的右边 else if (arr[mid] < target) { left = mid + 1; } // 如果中间元素大于目标元素,说明目标元素在左半部分,将右边界移动到中间元素的左边 else { right = mid - 1; } } // 如果查找范围为空,说明目标元素不存在,返回-1 return -1; } // 测试代码 let arr = [1, 3, 5, 7, 9, 11, 13, 15]; // 定义一个有序数组 let target = 9; // 定义要查找的元素 let index = binarySearch(arr, target); // 调用二分查找函数 console.log(index); // 输出结果,应该是4

二分查找的实现原理

  1. 首先,定义查找范围的左右边界,初始时为整个数组的范围,即左边界为0,右边界为数组的长度减1。
  2. 然后,计算查找范围的中间元素的索引,可以用左边界加右边界除以2的下取整来得到,例如,如果左边界是0,右边界是7,那么中间元素的索引是(0+7)/2=3.5,下取整是3。
  3. 接着,比较中间元素和目标元素,如果相等,说明找到了目标元素,返回中间元素的索引;如果不相等,说明目标元素在中间元素的左边或者右边,需要缩小查找范围。
  4. 如果中间元素小于目标元素,说明目标元素在中间元素的右边,那么将左边界移动到中间元素的右边,即左边界等于中间元素的索引加1,右边界不变,这样就缩小了查找范围的一半;如果中间元素大于目标元素,说明目标元素在中间元素的左边,那么将右边界移动到中间元素的左边,即右边界等于中间元素的索引减1,左边界不变,同样缩小了查找范围的一半。
  5. 重复第2步到第4步,直到找到目标元素或者查找范围为空,如果查找范围为空,说明目标元素不存在,返回-1。

总结

本文介绍了二分查找的定义、时间复杂度、实现原理和代码示例。

二分查找是一种在有序数组中查找目标元素的算法,它的时间复杂度是O(log n),比顺序查找的时间复杂度O(n)要快得多。

二分查找的实现原理是每次比较数组的中间元素和目标元素,如果相等则返回中间元素的索引,如果不相等则根据比较结果缩小查找范围,直到找到目标元素或者查找范围为空。

如果对你有用的话,可以打赏哦
打赏
ali pay
wechat pay

本文作者:CreatorRay

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!