二分查找思想

  1. 取已排列好数组的中间值
  2. 把需查找的值和中间值进行比较
  3. 如果比中间值小, 则对前半部分进行类似操作;如果比中间值大, 则对后半部分进行类似操作;

二分查找代码实现

// arr 为指定数组, target 为目标元素
function binarysearch(arr, target) {
let left = 0
let right = arr.length - 1
while (left <= right) {
const middlePoint = Math.floor((left + right) / 2)
let middle = arr[middlePoint]
if (middle > target) {
right = middlePoint - 1
} else if (middle < target) {
left = middlePoint + 1
} else {
return middle
}
}
return '数组中目标元素不存在'
}

以二分查找法看如何写出正确的程序

  • 明确变量的含义。比如在上述代码中, left 与 right 就是变量, 其意味当前查找数组中的左边界与右边界。[left, ...right];
  • 循环不变量。在上述代码中, 循环中改变变量(left, right)的取值, 但是不改变变量的含义。[left, ...right];
  • 小数据量调试。(快速, 准确, 耐心)
  • 大数据量调试。(能测出程序的性能)

真题

题目: 题目: 在一个二维数组中, 每一行都按照从左到右递增的顺序排序, 每一列都按照从上到下递增的顺序排序。请完成一个函数, 输入这样的一个二维数组和一个整数, 判断数组中是否含有该整数。

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
function find(arr, n) {
let x = 0
let y = arr[x].length - 1
while (x < arr.length && y > 0) {
if (n > arr[x][y]) {
x++
} else if (n < arr[x][y]) {
y--
} else {
return '找到目标元素'
}
}
return '目标元素不存在'
}

这道题严格不算是二分查找, 不过用到了类似的思维。

求开方

Leetcode : 69. Sqrt(x) (Easy)

思路: 满足 0 < sqrt < x && sqrt === x / sqrt, 转化为二分查找求 sqrt

/**
* @param {number} x
* @return {number}
*/
var mySqrt = function(x) { // 8
let left = 1
let right = x
while (left <= right) {
const mid = Math.floor((left + right) / 2) // 4 2 3
const sqrt = x / mid // 2 4 2.7
if (sqrt === mid) return sqrt
if (sqrt > mid) {
left = mid + 1 // 3
} else if (sqrt < mid) {
right = mid - 1 // 3 2
}
}
return right // 这里返回 right 而不是 left 的原因: 用了 Math.floor, mid 会偏小, 相应 sqrt 会偏大
}

有序数组的 Single Element

Leetcode : 540. Single Element in a Sorted Array (Medium)

题目描述: 一个有序数组只有一个数不出现两次, 找出这个数。