1. 1. 二分查找
  2. 2. 相关应用
    1. 2.1. 寻找边界值
    2. 2.2. 寻找区域
    3. 2.3. 轮转后的有序数组
【算法】二分查找
算法

二分查找

二分查找，也称折半查找，是一种在有序数组中查找特定元素的搜索算法。查找过程可以分为以下步骤：

  1. 从有序数组的中间元素开始搜索，如果该元素正好是目标元素，则搜索过程结束，否则进入下一步
  2. 如果目标元素大于或小于中间元素，则在数组大于或小于中间元素的那一半区查找，然后重复第一步的操作
  3. 如果某一步数组为空，则表示找不到目标元素

时间复杂度：O(logN)

JS代码实现方法：

  • 递归版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
function binarySearch (target, arr, start, end) {
  if (end > start) return -1
  start = start || 0
  end = end || arr.length - 1
  
  const mid = (start + end) >> 1
  if (target === arr[mid]) {
    return mid
  } else if (target > arr[mid]) {
    return binarySearch(target, arr, mid + 1, end)
  } else {
    return binarySearch(target, arr, start, mid - 1)
  }
}
  • 非递归版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function binarySearch (target, arr) {
  let start = 0,
      end = arr.length - 1
  
  while (end > start) {
    const mid = (start + end) >> 1
    if (target === arr[mid]) {
      return mid
    } else if (target > arr[mid]) {
      start = mid + 1
    } else {
      end = mid - 1
    }
  }
  return -1
}

相关应用

寻找边界值

在数组中寻找“正好大于（小于）目标数”的那个数。举例来说：

1
2
const arr = [2, 3, 5, 7, 11, 13, 17]
const target = 7

则目标7对应的上界值为11，而下界值为5。

  • 寻找上界
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function binarySearchUpperBound (target, arr) {
  let start = 0,
      end = arr.length - 1,
      mid = 0
  
  if (target >= arr[end]) return -1
  mid = (start + end) >> 1
  while (end > start) {
    if (arr[mid] > target) {
      end = mid
    } else {
      start = mid + 1
    }
    mid = (start + end) >> 1
  }
  return mid
}

与精确查找的不同之处在于，精确查找分成三类：大于，小于，等于（目标），而界限查找分成：大于和不大于。如果当前找到的树大于目标数时，它可能就是我们要找的数，所以需要保留这个索引，因此if (arr[mid] > target)时，end没有减1。

  • 寻找下界
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function binarySearchLowerBound (target, arr) {
  let start = 0,
      end = arr.length - 1,
      mid = 0
  
  if (target <= arr[start]) return -1
  mid = (start + end) >> 1
  while (end > start) {
    if (arr[mid] < target) {
      start = mid
    } else {
      end = mid - 1
    }
    mid = (start + end + 1) >> 1
  }
  return mid
}

由于end = mid - 1，如果使用向下取整，而arr[mid] < target又成立时，会导致start永远无法超过end而死循环。所以mid需要向上取整。

以上都是寻找严格界限，也就是大于或者小于。如果要寻找松散界限，大于等于或小于等于（即包含自身），只需要稍作修改：

去掉判断数组边界的等号：

1
target >= array[end] ==> target > array[end]

在与中间值的比较中加上等号：

1
arr[mid] > target ==> arr[mid] >= target

寻找区域

我们使用二分查找法时，都是基于数组中的元素各不相同这一条件的。假如存在重复数据，而数组依然有序，那么我们还是可以用二分查找法判断目标是否存在，只不过返回的index就只能是随机的重复数据中的某一个。

此时，我们希望知道有多少个目标数存在，或者说我们希望得到数组区域。

结合前面的界限查找，我们只要找到目标数的严格上界和严格下界，那么界限之间（不包括界限）的数据就是目标数的区域了。

1
2
3
4
5
6
7
8
function binarySearchRange (target, arr) {
  let lower = binarySearchLowerBound(target, arr)
  lower += 1
  if (target !== arr[lower]) return [-1, -1]
  let upper = binarySearchUpperBound(target, arr)
  upper = upper < 0 ? arr.length - 1 : upper - 1
  return [lower, upper]
}

轮转后的有序数组

二分查找法是要应用在有序数组上的，如果无序，那么比较和二分就没有意义了。

但是有一种特殊的数组上是可以应用的，那就是“轮转后的有序数组”。例如：

1
const arr = [7, 11, 13, 17, 2, 3, 5]

以上的数组就是以“5”为轴，将轴之前的数都轮转到数组的末尾所得到的新数组。非严格意义上来说，有序数组也属于轮转后的有序数组——取首元素为轴进行轮转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function binarySearchSortedArray (target, arr) {
  let start = 0,
      end = arr.length - 1
  
  while (start <= end) {
    const mid = (start + end) >> 1
    if (target < arr[mid]) {
      if (arr[mid] < arr[end]) { // 说明右半边是有序的
        end = mid - 1
      } else { // 说明左半边是有序的
        if (target < arr[start]) {
          start = mid + 1
        } else {
          end = mid - 1
        }
      }
    } else if (target > arr[mid]) {
      if (arr[start] < arr[mid]) { // 说明左半边是有序的
        start = mid + 1
      } else { // 说明右半边是有序的
        if (arr[end] < target) {
          end = mid - 1
        } else {
          start = mid + 1
        }
      }
    } else {
      return mid
    }
  }
  return -1
}
Previous post
Next post