二分查找法的一些理解
总字数941
阅读时长 ≈3 分钟
前言 🔗
做到一道简单的二分题
感觉很多都忘了
记了忘，忘了记
往返循环
二分查找 🔗
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。 但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。百度百科
题型 🔗
题型基本是建立在有序数组的寻找上 就我碰到的有三种
- 不重复数组找一个数K的索引
- 可能重复数组找一个数K的最左边的索引
- 可能重复数组找一个数K的最右边的索引
PS：这些题目的前提都是有序数组，并且是递增的
每次隔一阵子写就会出现莫名奇妙的死循环
不知道什么地方要加1
不知道判断要不要加=
所以写个帖子记录下
方便之后回忆
一般的二分查找法 🔗
javascript
/**
* @param nums 寻找的数组
* @param target 寻找的目标值
* @returns {number} 目标位置索引
*/
function binarySearch(nums, target) {
var length = nums.length;
var left = 0;
var right = length - 1;
var mid = 0;
while (left < right) {
mid = (left + right + 1) >>> 1;
if (target >= nums[mid]) {
// 如果目标值 >= mid对应的值，推出目标值处于右半区，且包括mid这个点
// 更新左边界
left = mid;
}
else if (target < nums[mid]) {
// 如果目标值 < mid对应的值，推出目标值处于左半区，且不包括mid这个点
// 更新右边界
right = mid - 1;
}
}
return nums[left] === target ? left : -1;
}不重复数组找K 🔗
javascript
/**
* @param nums 寻找的数组
* @param target 寻找的目标值
* @returns {number} 目标位置索引
*/
function binarySearch(nums, target) {
var length = nums.length;
var left = 0;
var right = length - 1;
var mid = 0;
while (left < right) {
mid = (left + right) >>> 1;
if (target === nums[mid]) {
// 找到，返回索引
return mid;
}
else if (target > nums[mid]) {
// 没找到，且目标值 > mid对应的值，推出此时值处于右分区
// 更新左边界
left = mid + 1;
}
else if (target < nums[mid]) {
// 没找到，且目标值 < mid对应的值，推出此时值处于左分区
// 更新右边界
right = mid - 1;
}
}
return nums[left] === target ? left : -1;
}重复数组找K的最左边 🔗
javascript
/**
* @param nums 寻找的数组
* @param target 寻找的目标值
* @returns {number} 目标位置索引
*/
function binarySearch(nums, target) {
var length = nums.length;
var left = 0;
var right = length - 1;
var mid = 0;
while (left < right) {
mid = (left + right) >>> 1;
if (target > nums[mid]) {
// 如果目标值 > mid对应的值，推出目标值在右分区，且不包括mid这个点
// 更新左边界
left = mid + 1;
}
else if (target <= nums[mid]) {
// 如果目标值 <= mid对应的值，推出目标值在左分区
// 此时如果是小于的话，表明在左分区，不包括mid这个点
// 此时如果是等于的话，表明找到，但是不确定是不是最左边的，所以也要搜索左分区
// 更新右边界
right = mid;
}
}
return nums[left] === target ? left : -1;
}重复数组找K的最右边 🔗
javascript
/**
* @param nums 寻找的数组
* @param target 寻找的目标值
* @returns {number} 目标位置索引
*/
function binarySearch(nums, target) {
var length = nums.length;
var left = 0;
var right = length - 1;
var mid = 0;
while (left < right) {
// 右边界收缩，所以用右中位数
mid = (left + right + 1) >>> 1;
if (target < nums[mid]) {
// 如果目标值 < mid对应的值，推出目标值在左半区，且不包括mid这个点
// 更新右边界
right = mid - 1;
}
else if (target >= nums[mid]) {
// 如果目标值 >= mid对应的值，推出目标值在右半区
// 此时如果是大于的话，表明在右分区，且不包括mid这个点
// 此时如果是等于的话，表明找到，但是不确定是不是最右边的，所以也要搜索右分区
// 更新左边界
left = mid;
}
}
return nums[left] === target ? left : -1;
}后记 🔗
越是简单感觉越容易写错emmm
#JavaScript
哦呐该，如果没有评论的话，瓦达西...