二分查找
Basic
在有序数组中二分查找target,返回索引index,未找到返回-1
- 循环
export const binarySearch = (arr = [], target) => {
let l = 0,
r = arr.length - 1
while (l <= r) {
let mid = (l + r) >> 1
if (arr[mid] == target) {
return mid
}
if (arr[mid] > target) {
r = mid - 1
} else {
l = mid + 1
}
}
return -1
}
- 递归
const binarySearch_recursive = (arr = [], target) => {
const search = (arr, target, l, r) => {
if (l > r) return -1
const mid = (l + r) >> 1
if (arr[mid] == target) return mid
if (arr[mid] > target) return search(arr, l, mid - 1, target)
return search(arr, mid + 1, r, target)
}
return search(arr, target, 0, arr.length - 1)
}
非递归算法在性能上有微弱优势
2
1
const res = binarySearch([2, 123, 432, 1829, 12123], 432)
2
console.log(res)
console结果可能不准确,按F12打开控制台查看
二分查找树
export class BST {
static Node(key, value) {
return {
key,
value,
left: null,
right: null
}
}
constructor() {
this.root = null
}
contain(key) {
return BST.contain(this.root, key)
}
insert(key, value) {
this.root = BST.insert(this.root, key, value)
}
search(key) {
return BST.search(this.root, key)
}
preOrder(key) { // 前序遍历
return BST.preOrder(this.root, key)
}
inOrder(key) { // 中序遍历
return BST.inOrder(this.root, key)
}
postOrder(key) { //后序遍历
return BST.postOrder(this.root, key)
}
levelOrder(key) { // 层序遍历
const q = []
q.push(this.root)
while (q.length !== 0) {
const node = q.pop()
if (node.key = key) return node.value
if (node.left) q.push(node.left)
if (node.right) q.push(node.right)
}
}
minmum() {
return BST.minmum(this.root)
}
maxmum() {
return BST.maxmum(this.root)
}
removeMin() {
if (this.root) {
BST.removeMin(this.root)
}
}
removeMax() {
if (this.root) {
BST.removeMax(this.root)
}
}
remove(key) {
const hasKey = this.contain(key)
if (!hasKey) return this.root
this.root = BST.remove(this.root, key)
}
static insert(node, key, value) {
if (node === null) {
return BST.Node(key, value)
}
if (key === node.key) {
node.value = value
} else if (key < node.key) {
node.left = BST.insert(node.left, key, value)
} else {
node.right = BST.insert(node.right, key, value)
}
return node
}
static contain(node, key) {
if (node == null) return false
if (key == node.key) return true
if (key < node.key) return BST.contain(node.left, key)
else return BST.contain(node.right, key)
}
static search(node, key) {
if (node == null) return null
if (key == node.key) return node.value
if (key < node.key) return BST.search(node.left, key)
else return BST.search(node.right, key)
}
static preOrder(node, key) {
if (node !== null) {
if (node.key == key) return node.value
BST.preOrder(node.left)
BST.preOrder(node.right)
}
}
static inOrder(node, key) {
if (node !== null) {
BST.inOrder(node.left)
if (node.key == key) return node.value
BST.inOrder(node.right)
}
}
static postOrder(node, key) {
if (node !== null) {
BST.postOrder(node.left)
BST.postOrder(node.right)
if (node.key == key) return node.value
}
}
static minmum(node) {
if (!node.left) return node
return BST.minmum(node.left)
}
static maxmum(node) {
if (!node.right) return node
return BST.maxmum(node.right)
}
// 删除掉以node为根的二分搜索树中的最小节点, 递归算法
// 返回删除节点后新的二分搜索树的根
static removeMin(node) {
if (!node.left) {
const rightNode = node.right
node = null
return rightNode
}
node.left = BST.removeMin(node.left)
return node
}
static removeMax(node) {
if (!node.right) {
const leftNode = node.left
node = null
return leftNode
}
node.right = BST.removeMax(node.right)
return node
}
// 删除掉以node为根的二分搜索树中键值为key的节点, 递归算法
// 返回删除节点后新的二分搜索树的根
static remove(node, key) {
if (!node) return null
if (key < node.key) {
node.left = BST.remove(node.left, key)
return node
} else if (key > node.key) {
node.right = BST.remove(node.right, key)
return node
} else {
if (!node.left) {
const rightNode = node.right
node = null
return rightNode
}
if (!node.right) {
const leftNode = node.left
node = null
return leftNode
}
// node->left != NULL && node->right != NULL
const successor = BST.minmum(node.right)
successor.left = node.left
successor.right = BST.removeMin(node.right)
node = null
return successor
}
}
}
58
1
const testBSTOrder = () => {
2
const bst = new BST()
3
const N = 1000000,
4
M = 1000000
5
const keyArr = []
6
for (let i = 0; i < N; i++) {
7
const key = ~~(Math.random() * M)
8
let res = bst.search(key)
9
if (!res) {
10
bst.insert(key, 1)
11
keyArr.push(key)
12
}
13
else {
14
res = res + 1
15
bst.insert(key, res)
16
}
17
}
18
console.time('search:')
19
bst.search(9983)
20
console.timeEnd('search:')
21
console.time('preOrder:')
22
bst.preOrder(9983)
23
console.timeEnd('preOrder:')
24
console.time('inOrder:')
25
bst.inOrder(9983)
26
console.timeEnd('inOrder:')
27
console.time('postOrder:')
28
bst.postOrder(9983)
29
console.timeEnd('postOrder:')
30
console.time('levelOrder:')
31
bst.levelOrder(9983)
32
console.timeEnd('levelOrder:')
33
}
34
testBSTOrder()
35
36
const testBSTSearch = () => {
37
const bst = new BST()
38
fetch('https://summaryofwork-1258044298.cos.ap-chengdu.myqcloud.com/public/txt/bible.txt')
39
.then(response => response.text())
40
.then(text => {
41
console.log('圣经总字数:' + text.length)
42
const wordsArr = text.replace(/\W+/g, ' ').split(/\s+/g)
43
// 词频统计
44
for (let word of wordsArr) {
45
let res = bst.search(word)
46
if (!res) bst.insert(word, 1)
47
else {
48
res = res + 1
49
bst.insert(word, res)
50
}
51
}
52
console.time('getWordsNum:')
53
bst.contain('God') ? console.log('God一共出现了' + bst.search('God') + '次') : console.log('不存在单词God')
54
console.timeEnd('getWordsNum:')
55
})
56
}
57
testBSTSearch()
58
console结果可能不准确,按F12打开控制台查看
← 基础必备之十大经典排序 中央定时器 →