这系列文章是慕课网《算法与数据结构》实战课程老师的讲授内容笔记整理，其中有很多动图都是我参考老师的动画演示自己制作的，并提供 JS(es6) 版的代码示例。代码仓库：📦 https://github.com/Mitscherlich/Play-with-Algorithms-JS

查找问题

二分查找法

// 二分查找法,在有序数组 arr 中,查找 target
// 如果找到 target, 返回相应的索引 index
// 如果没有找到 target, 返回 -1
Array.prototype.binarySearch = function (target) {
  const array = this.slice()
  const n = array.length
  // 在 arr[l...r] 之中查找 target
  let l = 0
  let r = n - 1
  while (l <= r) {
    // let mid = Math.floor((l + r) / 2)
    // 防止极端情况下的整形溢出，使用下面的逻辑求出 mid
    const mid = l + Math.floor((r - l) / 2)
    if (array[mid] === target) {
      return mid
    }
    if (target < array[mid]) {
      // 在 arr[l...mid] 之中查找 target
      r = mid - 1
    } else {
      // 在 arr[mid...r] 之中查找 target
      l = mid + 1
    }
  }
  return -1
}

使用递归实现二分查找法

function binarySearch (array, l, r, target) {
  if (l > r) {
    return -1
  }
  // let mid = Math.floor((l + r) / 2)
  // 防止极端情况下的整形溢出，使用下面的逻辑求出 mid
  const mid = l + Math.floor((r - l) / 2)
  if (array[mid] === target) {
    return mid
  } else if (target < array[mid]) {
    // 在 arr[l...mid] 之中查找 target
    return binarySearch(array, l, mid - 1, target)
  } else {
    // 在 arr[mid...r] 之中查找 target
    return binarySearch(array, mid + 1, r, target)
  }
}

Array.prototype.binarySearch = function (target) {
  const array = this.slice()
  const n = array.length
  return binarySearch(array, 0, n - 1, target)
}

floor 和 ceil

二分搜索树

二分搜索树的性质

1. 任意节点的左子树总是小于当前节点的值；

2. 任意节点的右子树总是大于当前节点的值；

3. 没有键值相等的节点。

// 二分搜索树中的节点的结构体
class Node {
  constructor (k, v) {
    this.key = k
    this.value = v
    this.left = null
    this.right = null
  }
}

// 二分搜索树
class BinarySearchTree {
  constructor () {
    this.root = null
    this.count = 0
  }
  // 返回二分搜索树的节点个数
  size () { return this.count }
  // 返回二分搜索树是否为空
  isEmpty () { return this.count === 0 }
  // 向二分搜索树中插入一个新的(k, v)数据对
  insert (k, v) {
    // TODO: 稍后实现
  }
  contain (k) {
    // TODO: 稍后实现
  }
  search (k) {
    // TODO: 稍后实现
  }
}

插入元素

1. 若带插入的树根节点 node 为空，则将带插入元素作为根节点插入；否则：

2. 若 k 等于 node.key，则更新 node.value 为 v；否则：

3. 若 k 小于 node.key，则将带 s 插入到 node 的左子树中；否则：

4. 将 s 插入到 node 的右子树中。

// 向以 node 为根的二分搜索树中, 插入节点 (k, v), 使用递归算法
// 返回插入新节点后的二分搜索树的根
function insert (node, k, v) {
  if (node === null) {
    return new Node(k, v)
  }
  if (k === node.key) {
    node.value = v
  } else if (k < node.key) {
    node.left = insert(node.left, k, v)
  } else {
    node.right = insert(node.right, k, v)
  }
  return node
}

class BinarySearchTree {
  ...
  insert (k, v) {
    this.root = insert(this.root, k, v)
    this.count += 1
  }
  ...
}

查找元素

1. 若 node 为空则查找失败；否则：

2. 若 v 等于 node.value 则查找成功；否则：

3. 若 v 小于 node.value，则搜索左子树；否则：

4. 重复 1-4，搜索右子树。

function contain (node, k) {
  if (node === null) {
    return false
  }
  if (k === node.key) {
    return true
  } else if (k < node.key) {
    return contain(node.left, k)
  } else {
    return contain(node.right, k)
  }
}

class BinarySearchTree {
  ...
  contain (k) { return contain(this.root, k) }
  ...
}

function search (node, k) {
  if (node === null) {
    return null
  }
  if (k === node.key) {
    return node.value
  } else if (k < node.key) {
    return search(node.left, k)
  } else {
    return search(node.right, k)
  }
}

class BinarySearchTree {
  ...
  search (k) { return search(this.root, k) }
  ...
}

小结

参考链接

• 二叉搜索树 - 维基百科