# 二分法查找

# 二分法(折半查找)

时间复杂度O(logn)级别的查找，在有序队列中使用
每次查找范围缩小一半，所以也叫折半查找

注意点：

循环退出条件
mid 的取值
low 和 high 的更新

终止条件、区间上下界更新方法、返回值选择

代码实现

const array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
// 基于递归的二分法查找
function search(arr, target, l = 0, r = arr.length - 1) {
  // 超限表示不存在
  if (l > r) return -1;
  // 取中
  let mid = (r + l) >>> 1
  if (arr[mid] == target) { // 相等
    return mid
  }
  if (arr[mid] < target) { // 右边
    return search(arr, target, mid + 1, r) // 右限[mid+1,r]
  }
  if (arr[mid] > target) { // 左边
    return search(arr, target, l, mid - 1) // 左限[l,mid-1]
  }
}
console.log(search(array, 6)) // -1
// 
function search(val, arr, l = 0, r = arr.length - 1) {
  if (l === r) return val === arr[l] ? l : -1
  let mid = l + (r - l >> 1)
  if (arr[mid] < val) {
    return search(val, arr, mid + 1, r)
  } else if (arr[mid] > val) {
    return search(val, arr, l, mid - 1)
  }
  return mid
}
----------------------------------------------
// 非递归二分法
function search(arr, target, l = 0, r = arr.length - 1) {
  let mid
  // 超限跳出
  while (l <= r) {
    mid = (r + l) >>> 1
    // 找到
    if (arr[mid] == target) {
      return mid
    }
    // 在右边
    if (arr[mid] < target) {
      // 改左限
      l = mid + 1 // [mid+1,r]
    }
    // 在左边
    if (arr[mid] > target) {
      // 改右限
      r = mid - 1 // [l,mid-1]
    }
  }
  // 未找到
  return -1
}
console.log(search(array, 6)) // -1

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

# 二分法查找重复值的索引

代码实现

function search(arr, target, l = 0, r = arr.length - 1) {
  let mid, res = []
  // 超限跳出
  while (l <= r) {
    mid = (r + l) >>> 1
    // 找到
    if (arr[mid] == target) {
      l = mid // 记录目标关键位置
      break
    }
    // 在右边
    if (arr[mid] < target) {
      // 改左限
      l = mid + 1 // [mid+1,r]
    }
    // 在左边
    if (arr[mid] > target) {
      // 改右限
      r = mid - 1 // [l,mid-1]
    }
  }
  while (arr[--l] == target && l >= 0); // 左界
  while (arr[++l] == target && l < arr.length) { // 右界
    res.push(l)
  }
  return res.length ? res : -1
}
console.log(search(array, 7)) // [3,4,5,6,7]

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

# 二分法求一个数的平方根，精确小数点后6位

给定一个数，求其平方根，最终计算出的数字精确小数点后6位

// 为了防止栈溢出，使用迭代循环
function sqrt(data) {
  let result = data / 2
  let res = result * result
  while (1) {
    if (res - data > 0.000001) {
      result = result - result / 2
    } else if (res - data < -0.000001) {
      result = result + result / 2
    } else {
      break
    }
    res = result * result
  }
  return result
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

除2比较

# 查找第一个值等于给定值的元素

在含有重复值的有序数组中查找

function search(data, arr) {
  let l = 0, r = arr.length - 1
  let mid = r >> 1
  while (l <= r) {
    if (arr[mid] < data) {
      l = mid + 1
      mid = l + (r - l >> 1)
    } else if (arr[mid] > data) {
      r = mid - 1
      mid = l + (r - l >> 1)
    } else {  // 重点
      if (mid === 0 || arr[mid - 1] !== data) return mid
      else mid -= 1
    }
  }
  return -1
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 查找最后一个值等于给定值的元素

在含有重复值的有序数组中查找

function search(data, arr) {
  let l = 0, r = arr.length - 1
  let mid = r >> 1
  while (l <= r) {
    if (arr[mid] < data) {
      l = mid + 1
      mid = l + (r - l >> 1)
    } else if (arr[mid] > data) {
      r = mid - 1
      mid = l + (r - l >> 1)
    } else {  // 区别
      if (mid === arr.length - 1 || arr[mid + 1] !== data) return mid
      else mid += 1
    }
  }
  return -1
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 查找第一个大于等于给定值的元素

在含有重复值的有序数组中查找

function search(data, arr) {
  let l = 0,
    r = arr.length - 1
  let mid = r >> 1
  while (l <= r) {
    if (arr[mid] >= data) { // 区别
      if (mid === 0 && arr[mid] >= data || arr[mid - 1] < data) return mid
      else r = mid - 1
    } else {
      l = mid + 1
    }
    mid = l + (r - l >> 1)
  }
  return -1
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 查找最后一个小于等于给定值的元素

在含有重复值的有序数组中查找

function search(data, arr) {
  let l = 0,
    r = arr.length - 1
  let mid = r >> 1
  while (l <= r) {
    if (arr[mid] <= data) { // 区别
      if (mid === arr.length-1 && arr[mid] <= data || arr[mid + 1] > data) return mid
      else l = mid + 1
    } else {
      r = mid - 1
    }
    mid = l + (r - l >> 1)
  }
  return -1
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

← 十大排序算法动态规划 →