Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

数据结构和算法躬行记(4)——二分查找

咖啡机(K.F.J) 2020-09-15 09:41:00 阅读数:114 评论数:0 点赞数:0 收藏数:0

二分查找(Binary Search)是对一种针对有序数据集合的查找算法,依赖数组,适合静态数据。通过 n/2^k=1(k 是比较次数),可以求得 k=log2^n,因此时间复杂度为高效地 O(logn)。

其思路很简单,就是每次与区间的中间数据做比较,缩小查找范围,但是期间涉及到的细节很容易踩坑,例如比较时是否带等号、mid值是否要加一等。例题:704. 二分查找

LeetCode的69. x 的平方根,x=sqrt(y); y=x^2,由于y和x是单调递增的,因此可用二分查找,每次取中值,不断逼近。另一种解题思路是牛顿迭代法。

在《剑指offer》一书中曾提到,写出高质量的代码需要了解3个方面:

(1)规范性,书写清晰、布局清晰和命名合理。

(2)完整性,完成基本功能、考虑边界条件、做好错误处理。

(3)鲁棒性,采取防御性编程、处理无效的输入。

下面是二分查找最基本的代码实现,改编自《二分搜索》,为了防止mid的溢出,才设计成了 low + Math.floor((high - low) / 2)。

function binarySearch(nums, target) {
let low = 0, high = ...;
while(...) {
let mid = low + ((high - low) >> 1);
if (nums[mid] == target) {
...
} else if (nums[mid] < target) {
low = ...
} else if (nums[mid] > target) {
high = ...
}
}
return ...;
}

其中占位符“...”处就是容易出错的细节部分:

(1)循环退出条件。

(2)low 和 high 的更新。

(3)找到目标值时的处理。

(4)函数的返回值。

一、无重复数据

在下面的binarySearch()函数中,nums是一个无重复数据的数组,需要注意:

(1)while循环的判断条件是小于等于,因为high的取值是末尾索引,相当于两端闭区间 [low, high]。

(2)当不匹配时,缩小查找区间,分成两块闭区间:[mid+1, high] 或 [low, mid-1]。

function binarySearch(nums, target) {
let low = 0,
high = nums.length - 1; //注意
while(low <= high) { //注意
let mid = low + ((high - low) >> 1);
if (nums[mid] == target) {
return mid; //注意
} else if (nums[mid] < target) {
low = mid + 1; //注意
} else if (nums[mid] > target) {
high = mid - 1; //注意
 }
}
return -1; //注意
}

面试题11 旋转数组的最小数字。二分查找的思路,用两个指针指向数组的第一个和最后一个元素,如果中间元素位于前面的递增子数组,那么它应该大于或等于第一个指针指向的元素。

面试题53 在排序数组中查找数字。用二分查找锁定指定值,然后在左右两边顺序扫描,直至找出第一个和最后一个指定值。延伸题:0~n-1 中缺失的数字

二、含重复数据

当查找的数组中包含重复数据时,二分查找需要做些处理。

面试题3 不修改数组找出重复数字。二分查找思想,从中间数字m分成两部分,1~m和m+1~n,如果1~m的数字超过m,那么区间有重复数字。

1)查找第一个等于给定值的元素

在下面的binarySearchLow()函数中,需要注意:

(1)while循环的判断条件是小于,因为 low 和 high 相等会陷入死循环。

(2)查找到匹配的数据不是立即返回,而是缩小范围,并且增加一次 high 的边界值判断。

(3)在跳出循环后,需要最终判断是否与目标值匹配。

function binarySearchLow(nums, target) {
let low = 0,
high = nums.length - 1;
while(low < high) { //注意
let mid = low + ((high - low) >> 1);
if (nums[mid] == target) {
high = mid - 1; //注意
if (nums[high] != target) //注意
return mid; //注意
} else if (nums[mid] < target) {
low = mid + 1;
} else if (nums[mid] > target) {
high = mid - 1;
}
}
return nums[low] == target ? low : -1; //注意
}

另一个类似的问题是查找最后一个等于给定值的元素,修改匹配时的范围,如下所示。

function binarySearchHigh(nums, target) {
let low = 0,
high = nums.length - 1;
while(low < high) {
let mid = low + ((high - low) >> 1);
if (nums[mid] == target) {
low = mid + 1; //注意
if (nums[low] != target) //注意
return mid; //注意
} else if (nums[mid] < target) {
low = mid + 1;
} else if (nums[mid] > target) {
high = mid - 1;
}
}
return nums[low] == target ? low : -1;
}

2)查找第一个大于等于给定值的元素

在下面的binarySearchLow()函数中,需要注意:

(1)修改匹配给定值的条件,变为大于等于。

(2)额外匹配一次 high 的边界值,成功时直接返回 mid。

(3)修改跳出循环后的匹配条件。

function binarySearchLow(nums, target) {
let low = 0,
high = nums.length - 1;
while(low < high) {
let mid = low + ((high - low) >> 1);
if (nums[mid] >= target) { //注意
high = mid - 1; //注意
if (nums[high] < target) //注意
return mid; //注意
} else if (nums[mid] < target) {
low = mid + 1;
}
}
return nums[low] >= target ? low : -1; //注意
}

另一个类似的问题是查找最后一个小于等于给定值的元素,修改匹配时的范围,如下所示。

function binarySearchHigh(nums, target) {
let low = 0,
high = nums.length - 1;
while(low < high) {
let mid = low + ((high - low) >> 1);
if (nums[mid] <= target) { //注意
low = mid + 1; //注意
if (nums[low] > target) //注意
return mid; //注意
} else if (nums[mid] > target) {
high = mid - 1;
}
}
return nums[low] <= target ? low : -1; //注意
}

本文的这些示例都没有经过大量测试用例的严谨验证,欢迎指正其中的潜在错误。

 

版权声明
本文为[咖啡机(K.F.J)]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/strick/p/13362536.html

支付宝红包,每日可领(支付宝免费1-2元支付红包)