网站开发周期安排,wordpress部署到sae,品牌设计作品集,成都市建设厅官方网站一、是什么
在计算机科学中#xff0c;二分查找算法#xff0c;也称折半搜索算法#xff0c;是一种在有序数组中查找某一特定元素的搜索算法
想要应用二分查找法#xff0c;则这一堆数应有如下特性#xff1a;
存储在数组中有序排序
搜索过程从数组的中间元素开始二分查找算法也称折半搜索算法是一种在有序数组中查找某一特定元素的搜索算法
想要应用二分查找法则这一堆数应有如下特性
存储在数组中有序排序
搜索过程从数组的中间元素开始如果中间元素正好是要查找的元素则搜索过程结束
如果某一特定元素大于或者小于中间元素则在数组大于或小于中间元素的那一半中查找而且跟开始一样从中间元素开始比较如果在某一步骤数组为空则代表找不到这种搜索算法每一次比较都使搜索范围缩小一半。 相比普通的顺序查找除了数据量很少的情况下二分查找会比顺序查找更快。
二、如何实现
基于二分查找的实现如果数据是有序的并且不存在重复项实现代码如下
function BinarySearch(arr, target) {if (arr.length 1) return -1// 低位下标let lowIndex 0// 高位下标let highIndex arr.length - 1while (lowIndex highIndex) {// 中间下标const midIndex Math.floor((lowIndex highIndex) / 2)if (target arr[midIndex]) {highIndex midIndex - 1} else if (target arr[midIndex]) {lowIndex midIndex 1} else {// target arr[midIndex]return midIndex}}return -1
} 如果数组中存在重复项而我们需要找出第一个制定的值实现则如下
function BinarySearchFirst(arr, target) {if (arr.length 1) return -1// 低位下标let lowIndex 0// 高位下标let highIndex arr.length - 1while (lowIndex highIndex) {// 中间下标const midIndex Math.floor((lowIndex highIndex) / 2)if (target arr[midIndex]) {highIndex midIndex - 1} else if (target arr[midIndex]) {lowIndex midIndex 1} else {// 当 target 与 arr[midIndex] 相等的时候如果 midIndex 为0或者前一个数比 target 小那么就找到了第一个等于给定值的元素直接返回if (midIndex 0 || arr[midIndex - 1] target) return midIndex// 否则高位下标为中间下标减1继续查找highIndex midIndex - 1}}return -1
}
实际上除了有序的数组可以使用还有一种特殊的数组可以应用那就是轮转后的有序数组
有序数组即一个有序数字以某一个数为轴将其之前的所有数都轮转到数组的末尾所得
例如[4, 5, 6, 7, 0, 1, 2]就是一个轮转后的有序数组
该数组的特性是存在一个分界点用来分界两个有序数组如下 分界点有如下特性
分界点元素 第一个元素分界点元素 第一个元素
代码实现如下
function search (nums, target) {// 如果为空或者是空数组的情况if (nums null || !nums.length) {return -1;}// 搜索区间是前闭后闭let begin 0,end nums.length - 1;while (begin end) {// 下面这样写是考虑大数情况下避免溢出let mid begin ((end - begin) 1);if (nums[mid] target) {return mid;}// 如果左边是有序的if (nums[begin] nums[mid]) {//同时target在[ nums[begin],nums[mid] ]中那么就在这段有序区间查找if (nums[begin] target target nums[mid]) {end mid - 1;} else {//否则去反方向查找begin mid 1;}//如果右侧是有序的} else {//同时target在[ nums[mid],nums[end] ]中那么就在这段有序区间查找if (nums[mid] target target nums[end]) {begin mid 1;} else {end mid - 1;}}}return -1;
};
对比普通的二分查找法为了确定目标数会落在二分后的哪个部分我们需要更多的判定条件。
三、应用场景
二分查找法的O(logn)让它成为十分高效的算法。不过它的缺陷却也是比较明显就在它的限定之上
有序我们很难保证我们的数组都是有序的数组数组读取效率是O(1)可是它的插入和删除某个元素的效率却是O(n)并且数组的存储是需要连续的内存空间不适合大数据的情况
关于二分查找的应用场景主要如下
不适合数据量太小的数列数列太小直接顺序遍历说不定更快也更简单每次元素与元素的比较是比较耗时的这个比较操作耗时占整个遍历算法时间的大部分那么使用二分查找就能有效减少元素比较的次数不适合数据量太大的数列二分查找作用的数据结构是顺序表也就是数组数组是需要连续的内存空间的系统并不一定有这么大的连续内存空间可以使用
