BinarySearch
使用二分的条件(整数二分、浮点数二分)
有单调性一定可以二分
能用二分解的题不一定具有单调性
有上下界
解题 3 步骤
预处理：如果集合未排序,则进行排序
二分查找：使用循环或递归在每次比较后将查找空间二分
先定义搜索区间
根据搜索区间定义循环结束条件
取中间元素和目标元素做对比(目标元素可能是需要找的元素或者是数组第一个/最后一个元素等)
根据比较的结果收缩区间,舍弃非法解
后处理：在剩余空间中确定可行的候选者
常见变体
如果存在多个满足条件的元素,返回最左边满足条件的索引
如果存在多个满足条件的元素,返回最右边满足条件的索引
数组不是整体有序的,比如先升序再降序,或者先降序再升序
将一维数组变成二维数组
。。。
framework
很多人喜欢拿整型溢出的 bug 说事儿,但是二分查找真正的坑根本就不是那个细节问题,而是在于到底要给 mid 加一还是减一,while 里到底用 <= 还是 <
分析二分查找代码时,最好不要出现 else,全部展开成 else if 方便理解
注意「搜索区间」和 while 的终止条件,如果存在漏掉的元素,记得在最后检查
如需定义左闭右开的「搜索区间」搜索左右边界,只要在
nums[mid] == target时做修改即可,搜索右侧时需要减一如果将「搜索区间」全都统一成两端都闭,好记,只要稍改
nums[mid] == target条件处的代码和返回的逻辑即可
some templates
1 Basic Template
//返回索引,arr必须提前排序
const binarySearch = (arr, target) => {
const len = arr.length
if (len === 0) return -1
let l = 0,
//Note 1
r = len - 1,
mid
//Note 2
while (l <= r) {
//Maybe note
mid = Math.floor(l + (r - l) / 2)
if (arr[mid] === target) {
return mid
} else if (arr[mid] < target) {
l = mid + 1
} else if (arr[mid] > target) {
//Note 3
r = mid - 1
}
}
//Maybe note
return -1
}2 查找第一个值等于给定值的元素(左边界)
//返回索引,arr必须提前排序
const binarySearchLeftBound = (arr, target) => {
const len = arr.length
if (len === 0) return -1
let l = 0,
r = len - 1,
mid
while (l <= r) {
mid = Math.floor(l + (r - l) / 2)
if (arr[mid] < target) {
l = mid + 1
} else if (arr[mid] > target) {
r = mid - 1
} else {
//已搜到第一个或已找到
//if (mid === 0 || arr[mid - 1] < target) {
if (mid === 0 || arr[mid - 1] !== target) {
return mid
//继续收缩右边界
} else {
r = mid - 1
}
}
}
return -1
}3 查找最后一个值等于给定值的元素(右边界)
//返回索引,arr必须提前排序
const binarySearch = (arr, target) => {
const len = arr.length
if (len === 0) return -1
let l = 0,
r = len - 1,
mid
while (l <= r) {
mid = Math.floor(l + (r - l) / 2)
if (arr[mid] < target) {
l = mid + 1
} else if (arr[mid] > target) {
r = mid - 1
} else {
//已搜到最后一个或已找到
//if (mid === len - 1 || arr[mid + 1] > target) {
if (mid === len - 1 || arr[mid + 1] !== target) {
return mid
} else {
l = mid + 1
}
}
}
return -1
}4 查找第一个大于等于给定值的元素
const binarySearch = (arr, target) => {
let l = 0,
r = arr.length - 1,
mid
while (l <= r) {
mid = Math.floor(l + (r - l) / 2)
if (arr[mid] >= target) {
if (mid === 0 || arr[mid - 1] < target) {
return mid
} else {
r = mid - 1
}
} else {
l = mid + 1
}
}
return -1
}5 查找最后一个小于等于给定值的元素
const binarySearch = (arr, target) => {
const len = arr.length
let l = 0,
r = len - 1,
mid
while (l <= r) {
mid = Math.floor(l + (r - l) / 2)
if (arr[mid] <= target) {
if (mid === len - 1 || arr[mid + 1] > target) {
return mid
} else {
l = mid + 1
}
} else {
r = mid - 1
}
}
return -1
}6 寻找左侧边界的二分搜索(labuladuo version)
const leftBound = (arr, target) => {
let l = 0,
//Note 1
r = arr.length - 1
//Note 2
while (l <= r) {
let mid = Math.floor(l + (r - l) / 2)
if (arr[mid] < target) {
//Note 3
l = mid + 1
} else if (arr[mid] > target) {
//Note 3
r = mid - 1
} else if (arr[mid] === target) {
//Note 3
r = mid - 1
}
}
//Note 4
//检查出界情况
if (l >= arr.length || arr[l] !== target) return -1
return l
}7 寻找右侧边界的二分搜索(labuladuo version)
const rightBound = (arr, target) => {
let l = 0,
r = arr.length - 1
while (l <= r) {
let mid = Math.floor(l + (r - l) / 2)
if (arr[mid] < target) {
l = mid + 1
} else if (arr[mid] > target) {
r = mid - 1
} else if (arr[mid] === target) {
l = mid + 1
}
}
if (r < 0 || arr[r] !== target) return -1
return r
}questions
var search = function (nums, target) {
const len = nums.length
if (len === 0) return -1
let l = 0,
r = len - 1,
mid
while (l <= r) {
mid = Math.floor(l + (r - l) / 2)
if (nums[mid] === target) return mid
//看左边
//in case mid === l 即下标相等
//[start, mid]有序
if (nums[mid] >= nums[l]) {
if (target < nums[mid] && target >= nums[l]) {
r = mid - 1
} else {
l = mid + 1
}
// [mid, end]有序
} else {
if (target > nums[mid] && target <= nums[r]) {
l = mid + 1
} else {
r = mid - 1
}
}
}
return -1
}const binarySearch = (nums, target, lower) => {
let l = 0,
r = nums.length - 1,
ret = nums.length
while (l <= r) {
const mid = Math.floor((l + r) / 2)
if (nums[mid] > target || (lower && nums[mid] >= target)) {
r = mid - 1
ret = mid
} else {
l = mid + 1
}
}
return ret
}
var searchRange = function (nums, target) {
const ret = [-1, -1]
const leftIdx = binarySearch(nums, target, true)
const rightIdx = binarySearch(nums, target, false) - 1
if (
leftIdx <= rightIdx &&
rightIdx < nums.length &&
nums[leftIdx] === target &&
nums[rightIdx] === target
) {
ret = [leftIdx, rightIdx]
}
return ret
}var mySqrt = function (x) {
if (x < 2) return x
let l = 0,
r = x,
mid
while (l <= r) {
mid = Math.floor(l + (r - l) / 2)
if (mid * mid < x) {
l = mid + 1
} else if (mid * mid > x) {
r = mid - 1
} else {
return mid
}
}
//l > r即l = r + 1，返回较小数
return r
}var search = function (nums, target) {
const len = nums.length
if (len === 0) return false
let l = 0,
r = len - 1,
mid
while (l <= r) {
mid = Math.floor(l + (r - l) / 2)
if (nums[mid] === target) return true
//move left pointer to exclude repeat item, or we can not define the monotonic section
if (nums[l] === nums[mid]) {
l++
continue
}
if (nums[mid] >= nums[l]) {
if (target < nums[mid] && target >= nums[l]) {
r = mid - 1
} else {
l = mid + 1
}
} else {
if (target > nums[mid] && target <= nums[r]) {
l = mid + 1
} else {
r = mid - 1
}
}
}
return false
}var findMin = function (nums) {
const len = nums.length
if (len === 0) return null
if (len === 1) return nums[0]
let l = 0,
r = len - 1,
mid
//in case array is a sorted array
if (nums[r] > nums[l]) return nums[0]
while (l <= r) {
mid = Math.floor(l + (r - l) / 2)
//judge according to nums[mid]
if (nums[mid] < nums[mid - 1]) return nums[mid]
if (nums[mid] > nums[mid + 1]) return nums[mid + 1]
//看右边
if (nums[mid] < nums[len - 1]) {
r = mid - 1
} else {
l = mid + 1
}
}
return null
}
//better
var findMin = function (nums) {
let l = 0
let r = nums.length - 1
while (l < r) {
const mid = l + Math.floor((r - l) / 2)
//所有数据不重复，即不存在(nums[mid] === nums[r]的情况
//看右边
if (nums[mid] < nums[r]) {
r = mid
} else {
l = mid + 1
}
}
return nums[l]
}var isPerfectSquare = function (num) {
if (num < 2) return num
let l = 0,
r = num,
mid
while (l <= r) {
mid = Math.floor(l + (r - l) / 2)
if (mid * mid < num) {
l = mid + 1
} else if (mid * mid > num) {
r = mid - 1
} else if (mid * mid === num) {
return true
}
}
return false
}
//数学
var isPerfectSquare = function (num) {
let x = 1,
square = 1
while (square <= num) {
if (square === num) return true
x++
square = x * x
}
return false
}Last updated