Repository navigation
腾讯：简述二分查找算法与时间复杂度，并实现一个二分查找算法 #83
Description
二分查找也称折半查找算法，它是一种简单易懂的快速查找算法。例如我随机写0-100之间的一个数字，让你猜我写的是什么？你每猜一次，我就会告诉你猜的大了还是小了，直到猜中为止。
该算法要求待查找的数组已排序，实现步骤如下：
- 选择数组中的中间数
- 查找数与中间数对比，比中间数低，则去中间数左边的子数组中寻找；比中间数高，则去中间数右边的子数组中寻找；相等则返回查找成功
- 重复上一步，知道查找成功或失败
function binarySearch(items, item) {
var low = 0,
high = items.length - 1,
mid, elem
while(low <= high) {
mid = Math.floor((low+high)/2)
elem = items[mid]
if(elem < item) {
low = mid + 1
} else if(elem > item) {
high = mid - 1
} else {
return mid
}
}
return -1
}
// 测试
var arr = [2,3,1,4]
// 快排
quickSort(arr)
binarySearch(arr, 3)
// 2
binarySearch(arr, 5)
// -1测试成功
二分查找易错点：
- 循环退出条件是
low <= high，注意是<= mid的取值是Math.floor((low+high)/2)lowhigh每次更新的时候，low = mid + 1high = mid - 1
二分查找局限性：
- 针对的对象是数组结构，因为是通过下标来随机访问元素
- 数组必须有序
- 数组太小不合适，直接使用顺序查找即可
- 数组太长不合适，数组要求连续的内存空间，数组太长不利于存储
时间复杂度： O(logn)
空间复杂度：O(1)
Activity
BruceYuj commentedon Jul 16, 2020
第一次在 瓶子君这边写题解。
二分查找我更加喜欢 C++ STL 里面的 lower_bound 写法，可以最大语义化的实现二分查找。
变体：查找最后一个小于 target 的位置，返回
left-1即可