二分查找

发表于 | 分类于

二分查找适合在一个有序数组种查找目标值，判断目标值是否存在

以下代码采用二分查找法，在有序数组种查找指定值，找到则返回索引，否则返回 -1：

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function binarySearch (arr, n, target) {
  let l = 0
  let r = n - 1
  while (l <= r) {
  	let mid = l + Math.floor((r - l) / 2)
    if (arr[mid] === target) {
      return mid
    } else if (arr[mid] > target) {
      r = mid - 1
    } else {
      l = mid + 1
    }
  }
  return -1
}

let testArray = [10,20,30,40,50,60,70,80,90,100]
console.log(binarySearch(testArray, 10, 20))

上面代码需要注意的地方是 while 里面的 l <= r, 是 <=，并且是闭区间。

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function binarySearch (arr, n, target) {
  let l = 0
  let r = n - 1
  let result = -1
  const search = function (target, l, r) {
  	let mid = l + Math.floor((r - l) / 2)
    if (arr[mid] === target) {
      result = mid
      return mid
    } else if (arr[mid] > target) {
      return search(target, l, mid - 1)
    } else {
      return search(target, mid + 1 , r)
    }
    return -1
  }
  return search(target, l, r)
}

let testArray = [10,20,30,40,50,60,70,80,90,100]
console.log(binarySearch(testArray, 10, 90))