你有没有碰到过这样的情况,当刷题的时候,刚开始满头雾水不知道从何下手,然后匆匆忙忙的看了题解。哦~是这样啊,然后开始按照题解的思路答题。答到了一半发现不会了,又看了看题解,最后终于答出来了。看看了实现的代码,一步、两步、三步、四步···这也不难啊。
突然有一天面试了,问到了你曾刷到的题目,此时你只记得你曾经刷过了~。思路全忘了。
我也经常碰到这种境况,我也承认我是个算法小菜鸡。所以我打算用文章的形式记录我学习算法的过程。也算是一种输出吧。有大佬说啊“学习算法就像是做数学题,记住公式,碰到题目想想是属于哪一种,开始套公式。”那咱们就试试吧!
二分查找在我们学习算法中是很重要的一部分,而且面试的时候会经常的让我们手写一些算法。
探究几个最常用的二分查找场景:寻找一个数、寻找左侧边界、寻找右侧边界
二分查找公式
function binarySearch(nums, target) {
let left = 0
let right = ...
while(...) {
const mid = Math.floor(left + (right - left) / 2)
if(nums[mid] === target) {
...
} else if(nums[mid] < target) {
left = ...
} else if(nums[mid] > target) {
right = ...
}
}
return ...
}
分析二分查找技巧 不要出现else
,而是把所有情况用else if
写清楚,这样可以清楚的展示所有细节。
Math.floor(left + (right - left) / 2)
其实和Math.floor((left +right)/2)
的结果是一样的。如果left
和right
很大的时候,相加会导致移除。Math.floor(left + (right - left) / 2)
可以有效的防止溢出。
寻找一个数
var search = function (nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] === target) {
return mid;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
return -1;
};
力扣第704题二分查找 这题是二分查找最简单的题型,几乎所有的二分查找的题型都是根据这个拓展的。
我们首先考虑的是搜索区间。因为定义的right
为nums.length - 1
,所以搜索区间为[left, right]
两端都闭。当查找到了目标元素,则停止搜索退出循环,然后返回目标值对应的索引。
当没有找到目标元素,循环的终止条件为left === right + 1
的时候,直接返回-1即可。
缺陷
如果给你个有序数组nums = [1,2,2,2,3]
,target
为2,此时用上面的方法返回的索引是2。如果我们想得到的target
的在nums
中最左边满足条件的值,或者最右边满足条件的值,这种方法就有问题了。
可能会想到,当找到了target
的值,然后向左,向右做线性搜索。但是这样就很难保证二分查找对数级的复杂度了。
寻找最左边满足条件的值
方式一
function leftBound(nums, target) {
let left = 0;
let right = nums.length;
while (left < right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] === target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
if (left === num.length) return -1;
return nums[left] === target ? left : -1;
}
上面是一种比较常见的代码形式。但是和我们刚开始的框架是可以匹配的。在这里while中使用的<
,而不是<=
。因为我们在定义right
的时候,是nums.length
而不是nums.length-1
。那就说明我们的搜索区间是在[left,right)
左闭右开。所以终止条件就是当left == right
的时候。
还会发现一个不一样的地方,right = mid
而不是right = mid - 1
,这个还是受上面的搜索区间的影响。因为搜索区间为[left,right)
左闭右开,所以当nums[mid]
被检测到的时候,下一步应该缩小搜索区间。当nums[mid] === target
的时候,虽然已经找到了target
的值,但是不要立即返回,而是缩小搜索区间为[left, mid)
。然后不断的向左边收缩,直到锁定左侧边界,也就是当left == right
的时候。
最后,考虑下越界情况,当left
的值为nums.length
的时候说明查找左侧边界已经超出了搜索区间,说明target
的值比所有数都大。当left
的值为target
的时候,说明找到了直接返回即可。然后其实返回left
和返回right
都一样,因为我们的终止条件是left == right
。
方式二
function leftBound(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] === target) {
right = mid - 1;
}
}
if (left >= nums.length || nums[left] != target) {
return -1;
}
return left;
}
方式一的搜索区间为[left, right)
。我们方式二的搜索区间改为[left, right]
左闭右闭。因为right
的取值为nums.length - 1
是nums
的最后一个值。while
的终止条件则为left == right + 1
,也就是代码中用的<=
。
此时right = mid - 1
而不是right = mid
, 因为搜索区间变了,[left,right]
两边都闭。
最后判断一下边界条件,如果left >= nums.length
说明已经超出了搜索区间,或者呢left
的值和target不一样说明没找到。
这样就和第⼀种⼆分搜索算法统⼀了,都是两端都闭的搜索区间,⽽且最后返回的也是left
变量的值。不过我还是比较倾向于这种。哈哈。
寻找最右侧满足条件的值
方式一
function rightBound(nums, target) {
let left = 0;
let right = nums.length;
while (left < right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] === target) {
left = mid + 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
if (left === 0) return -1;
return nums[left + 1] === target ? left - 1 : -1;
}
这种方式和寻找左侧边界类似,还是使用搜索区间为[left, right)
左闭右开的方式。关键的点在于当nums[mid]=== target
的时候,设置的是left=mid+1
。这样就可以把搜索区间变为[mid+1, right)
。利用这种方式不断的增大左边界left
的值,是的区间不断的向右靠拢,最后到达右边界。
但是这种方式最后返回的是left - 1
。因为while
的终止条件是left === right
,此时循环已经退出,如果已经找到了,那么left
的则比要锁定的目标索引多1。因为下面这段代码
if(nums[mid] === target) {
left = mid + 1
}
所以最后的目标值要left - 1
方式二
function rightBound(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] === target) {
left = mid + 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
if (right < 0 || nums[right] !== target) {
return -1;
}
return right;
}
这里和类似左侧边界的搜索区间[left, right]
左闭右闭。
其实二分查找差不多也就是这三种情况,你也可以理解为就是一种情况,然后不断的延伸。那我们记住套路了就开始去刷题巩固一下吧!
以上就是JavaScript中二分查找的例题详解的详细内容,更多关于JavaScript二分查找的资料请关注编程网其它相关文章!