腾讯:简述二分查找算法与时间复杂度,并实现一个二分查找算法
sisterAn opened this issue · 1 comments
sisterAn commented
二分查找也称折半查找算法,它是一种简单易懂的快速查找算法。例如我随机写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)
low
high
每次更新的时候,low = mid + 1
high = mid - 1
二分查找局限性:
- 针对的对象是数组结构,因为是通过下标来随机访问元素
- 数组必须有序
- 数组太小不合适,直接使用顺序查找即可
- 数组太长不合适,数组要求连续的内存空间,数组太长不利于存储
时间复杂度: O(logn)
空间复杂度:O(1)
BruceYuj commented
第一次在 瓶子君这边写题解。
- 二分查找,顾名思义,就是不断将数据范围(假设为 n)分成两部分,这两个部分就分别成了性质相同的子问题(数据规模为 n/2)。往往根据题意,我们能直接去掉其中一个子问题。这样不断分割,直到遇到最小可以直接解决的子问题,回溯。
- 时间复杂度: O(logn)
二分查找我更加喜欢 C++ STL 里面的 lower_bound 写法,可以最大语义化的实现二分查找。
- 查找是否存在指定的数
function find(nums, target) {
let left = 0;
let right = nums.length; // 范围是 [left, right)
while(left < right) {
let mid = left + Math.floor((right-left)/2);
if(nums[mid] < target) {
left = mid+1;
} else {
right = mid;
}
}
return left !== nums.length && nums[left] === target; // 如果元素存在并且重复,则left指向重复的第一个一个位置;如果不存在,则left返回的是可以插入的位置。
}
- 查找第一个大于或等于 target 的位置:
function find(nums, target) {
let left = 0;
let right = nums.length; // 范围是 [left, right)
while(left < right) {
let mid = left + Math.floor((right-left)/2);
if(nums[mid] < target) {
left = mid+1;
} else {
right = mid;
}
}
return left;
}
变体:查找最后一个小于 target 的位置,返回 left-1
即可