Binary Search
- Sorted(单调递增或者递减)
- Bounded(存在上下界)
- Accessible by index(能够通过索引访问)
二分查找代码
left, right = 0, len(array) - 1
while left <= right:
mid = (left + right) / 2
if array[mid] == target:
# find the target
break or return result
elif array[mid] < target:
left = mid + 1
else:
right = mid - 1
实战题⽬
共 3 题
- https://leetcode.com/problems/sqrtx/
- 【第 367 题-有效的完全平方数】
// 方法一： 暴力法
/**
* @param {number} num
* @return {boolean}
*/
var isPerfectSquare = function(num) {
let i = 1
while (i * i < num) {
i += 1
}
return i * i == num
}
// 时间复杂度 O(sqrt(N))
// 方法二：二分查找法
/**
* @param {number} num
* @return {boolean}
*/
var isPerfectSquare = function(num) {
let left = 1,
right = num,
mid
while (left < right) {
mid = parseInt((left + right) / 2)
if (mid * mid < num) {
left = mid + 1
} else {
right = mid
}
}
return left * left == num // 为什么是left * left
// 时间复杂度： O(log(N))
}
- https://www.beyond3d.com/content/articles/8/ (扩展阅读)