前端算法leetcode-二分查找
前端算法leetcode-二分查找
0 前言
记录前端学习!
1 二分查找
前提条件:
- 有序
- 只查找一个而不是多个
核心思想:(默认数组递增)
对于有序数组想要查询到目标,首先将数组中间值与目标比对,如果比配成功,皆大欢喜!如果不等,则可以排除掉一半的不符合数据,将此过程不断迭代,最终找到目标或是返回无目标,查询失败。
整体时间复杂度为:
o ( log n ) o( \log_{}{n} ) o(logn)
边界问题:与target比较的中间数字是否要加入到下次查找中?
因此,二分查找中目标元素对应区间的定义十分重要:
1. [left,right]
- 循环条件:while(left <= right)
- 判断 if(nums[middle] > target) right = middle -1
2. [left,right)
- 循环条件:while(left < right)
- 判断 if(nums[middle] > target) right = middle
2 算法应用(Leetcode)
704.二分查找(经典)
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function(nums, target) {
let left = 0
let right = nums.length - 1
while (left <= right){
const middle = Math.floor((left + right) / 2)
if(nums[middle] === target){
return middle
}else if(nums[middle] < target){
left = middle + 1
}else if(nums[middle] > target){
right = middle - 1
}
}
return -1
};
tips:
- Math.floor() 函数总是返回小于等于一个给定数字的最大整数。
35.搜索插入位置
【思路】等价于查找大于等于target的最小下标,即相当于返回left
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function (nums, target) {
let left = 0
let right = nums.length - 1
while (left <= right) {
let middle = left + ((right - left) >> 1)
if (nums[middle] === target) {
return middle
} else if (nums[middle] > target) {
right = middle - 1
} else if (nums[middle] < target) {
left = middle + 1
}
}
return left
};
tips:
- left + ((right -left) >> 1) == (left + right) /2,但为什么不直接用(left + right) /2 而用left + ((right -left) >> 1),因为left + right 在某种情况下可能会超过基本类型所能容纳的最大值,而且 >> (位运算) 比 / 运算要快一点,血泪教训要注意加括号!!
34. 在排序数组中查找元素的第一个和最后一个位置
【思路】要找的就是数组中第一个等于target的位置(l)和第一个大于target的位置减1(r)
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function (nums, target) {
let left = 0
let right = nums.length - 1
let l = -1
let r = -1
// 找出第一个target下标
while (left <= right) {
let middle = left + ((right - left) >> 1)
if (nums[middle] === target) {
l = middle
right = middle - 1
} else if (nums[middle] > target) {
right = middle - 1
} else if (nums[middle] < target) {
left = middle + 1
}
}
// 找到最后一个等于target的下标
left = 0
right = nums.length - 1
while (left <= right) {
let middle = left + ((right - left) >> 1)
if (nums[middle] === target) {
r = middle
left = middle + 1
} else if (nums[middle] > target) {
right = middle - 1
} else if (nums[middle] < target) {
left = middle + 1
}
}
return [l, r]
};
tips:
- 注意标黄两行的逻辑,要确保在nums[middle]===target时,找第一个和最后一个时都能够找到最端部
852.山脉数组的峰顶索引
/**
* @param {number[]} arr
* @return {number}
*/
var peakIndexInMountainArray = function (arr) {
let left = 1
let right = arr.length - 2
while (left <= right) {
let mid = left + ((right - left) >> 1)
if (arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1]) {
return mid
} else if (arr[mid] > arr[mid + 1] && arr[mid] < arr[mid - 1]) {
right = mid - 1
} else if (arr[mid] < arr[mid + 1]) {
left = mid + 1
}
}
};
tips:
- 可以依据题目条件,适当缩小查找范围
367.有效的完全平方数
【思路】不断迭代查找是否满足平方等于目标数,运用二分查找
/**
* @param {number} num
* @return {boolean}
*/
var isPerfectSquare = function (num) {
let left = 1
let right = num
while (left <= right) {
let mid = left + ((right - left) >> 1)
if (mid * mid === num) {
return true
} else if (mid * mid < num) {
left = mid + 1
} else {
right = mid - 1
}
}
return false
};
原文地址:https://blog.csdn.net/Hola__SUN/article/details/136115564
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!