头条前端面经之算法题,二分查找

来自于2019年10月, 头条前端面试, 手写二分查找

二分查找(binary search)是一种高效的查找方法,利用了一分为二、分而治之的算法思想

但是也有两个前提条件,才能用二分查找:

  • 必须使用顺序存储结构(也可以理解为允许随机访问的方式)
  • 必须按关键字有序排列,(如果是随机的排列,就不适用二分查找了)

二分查找的具体分析

给个题目:
是要在有序序列
2 12 23 43 66 98 100
中查找指定的一个数,假如 100

用算法怎么实现呢?

暴力法

遍历有序序列,肯定能查找到这个数

1
2
3
4
5
6
7
8
9
function search(arr, target) {
for (var i = 0; i < arr.length; ++ i) {
if (arr[i] === target) {
return i
}
}

return -1
}

1
search([2, 12, 23, 43, 66, 98, 100],  100)

OK,很好这个方法肯定能实现查找

那我们来分析下这个算法的复杂度(算法好与坏,通过复杂度来分析)

这个算法查找方法,通过遍历数组实现,其时间复杂度是 O(n),其中n是指有序序列的长度级别

那我们有没有更好的方式呢?比 O(n) 还优的时间复杂度?

二分查找法

首先,我们来看个图片(图片来源于网络)
有序列表

我们先看图片第一行,是有序序列(假设是升序序列),二分查找法怎么找 100 呢?假设目标数目 target = 100

1、取 target 和当前有序序列的中间数比较
2、如果相等,则说明找到
3、如果不等,且 target 比中间数小,则说明 target 肯定在中间数的左边区间(为什么呢,因为序列是从小到大排列的,既然target比中间数小,那target肯定在左侧区间啊)
4、那问题是不是演变成在这个中间数的左边区间(5 12 23),继续查找 target 了,重复 1 2 3 的过程
5、如果不等,且 target 比中间数大,则说明 target 肯定在中间数的右边区间,其操作类似于 步骤 4

我们以 2, 12, 23, 43, 66, 98, 100 查找 100 为例

1、100 和序列中间数 43 比较
2、100 比 43 大,说明在 43 右边区间
3、继续在 66, 98, 100 查找 100,
4、100 和新序列中间数 98 比较
5、100 比 98 大,说明在 98 的右边区间
6、继续在新序列 100 中查找 100
7、100 和 中间数 100 相等,找到,结束

继续我们以 2, 12, 23, 43, 66, 98, 100 查找 80 为例

1、80 和序列中间数 43 比较
2、80 比 43 大,说明在 43 右边区间
3、继续在 66, 98, 100 查找 80,
4、80 和新序列中间数 98 比较
5、800 比 98 小,说明在 98 的左边区间
6、继续在新序列 66 中查找 80
7、80 和 中间数 66 比较
8、80 比 66 大,说明在 66 右边区间
9、继续在新序列 [] 中查找 80
10、此时序列为空,查找结束,查找失败,返回 -1

理解算法思想后,我们来开始编程coding了

二分查找算法的Javascript代码

递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* 二分查找法
* @param: arr 有序序列
* @param: taret 我们要查找的目标数
* @return: 如果找到,返回下标索引,否则返回 -1
*/
function binarySearch(arr, target) {
return recursion(arr, 0, arr.length - 1, target)
}

/**
* 递归查找
* @param: arr 有序序列的完整序列
* @param: 当前查找的子序列的左下标索引
* @param: 当前查找的子序列的右下标索引
* @param: taret 我们要查找的目标数
* @return: 如果找到,返回下标索引,否则返回 -1
*/
function recursion(arr, left, right, target) {
if (left > right) {
// left > right,说明这个子序列是空的
return -1
}

let mid = Math.ceil(left + (right - left) / 2);
if (target === arr[mid]) {
// 找到目标数,返回下标 mid
return mid;
} else if (target < arr[mid]) {
// target 比中间数小,说明在中间数左边区间,即 [left, mid - 1]
return recursion(arr, left, mid - 1, target);
} else {
// target 比中间数大,说明在中间数右边区间,即 [mid + 1, right]
return recursion(arr, mid + 1, right, target);
}
}

我们再看下非递归版本,非递归版本反而更常见

非递归版本的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* 二分查找法
* @param: arr 有序序列
* @param: taret 我们要查找的目标数
* @return: 如果找到,返回下标索引,否则返回 -1
*/
function binarySearch(arr, target) {
// 初始状态下,查询的有序序列在数组的范围是 0 - arr.length-1
let left = 0;
let right = arr.length - 1;

while (left <= right) {
// 注意这里是计算中间数的下标索引,
// 由于序列长度可能是奇数、也可能是偶数,
// 因此 (right - left) / 2 会产生小数点位
let mid = Math.ceil(left + (right - left) / 2);

if (target === arr[mid]) {
// 找到目标数,返回下标 mid
return mid;
} else if (target < arr[mid]) {
// target 比中间数小,说明在中间数左边区间,即 [left, mid - 1]
// 这个时候,只要缩小查找的有序序列范围到 left - mide-1 即可
right = mid - 1;
} else {
// target 比中间数大,说明在中间数右边区间,即 [mid + 1, right]
// 这个时候,只要缩小查找的有序序列范围到 mid+1 - right 即可
left = mid + 1;
}
}

// 这里代表没找到,返回 -1
return -1
}

接下来,我们来看下这种算法的复杂度分析

由于二分查找的路径类似于一个二叉查找树从根到叶子节点的路径,这个路径长度是 O(log2(n))

因此二分查找的时间复杂度是 O(log2(n))

两种算法比较

暴力法的时间复杂度是 O(n)

二分查找法的时间复杂度是 O(log2(n))

n 大于 log2(n)

因此从时间复杂度的角度来说,二分查找法 更优

更多前端面试题和算法题,请搜索微信小程序 前端面试精华
前端面试精华
前端面试精华

坚持原创技术分享,谢谢鼓励我继续创作!