《大话数据结构》第8章，查找

一.顺序查找

顺序查找：线性查找

1
2
3
4
5
6
7
8
function sequentialSearch(arr, key) {
    for (var i = 0, len = arr.length; i < len; i++) 
        if(arr[i] === key)
            return i
    return -1;
}
sequentialSearch([0, 1, 16, 24, 35, 47, 59, 62, 73, 88, 99], 62)

二.有序表查找

  • 折半查找

折半查找: 又称二分查找，在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function binarySearch(arr, val) {
    var low = 0, high = arr.length - 1, mid
    while (low <= high) {
        mid = Math.ceil((low + high)/2)
        if (arr[mid] < val) {
            low = mid + 1 
        } else if (arr[mid] > val) {
            high = mid - 1
        } else {
            return mid
        }
    }
    return -1
}
binarySearch([0, 1, 16, 24, 35, 47, 59, 62, 73, 88, 99], 62)
  • 插值查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function interpolationSearch(arr, val) {
    var low = 0, high = arr.length - 1, mid
    while (low <= high) {
        lowVal = arr[low], highVal = arr[high]
        mid = parseInt( low + (val - lowVal)/(highVal - lowVal) * (high - low) )
        console.log(mid)
        if (arr[mid] < val) {
            low = mid + 1 
        } else if (arr[mid] > val) {
            high = mid - 1
        } else {
            return mid
        }
    }
    return -1
}
interpolationSearch([0, 1, 16, 24, 35, 47, 59, 62, 73, 88, 99], 62)
  • 斐波那契查找

三.线性索引查找

四.二叉排序树

五.平衡二叉树（AVL树）

六.多路查找树