有序表查找之二分查找

发表于 分类于 / Changyan：

简介

二分查找又名折半查找。它的前提是所操作的数据集是一个有序的数据集。它的基本思想是：开始时，先找出有序集合中间的那个元素。如果此元素比要查找的元素大，就接着在较小的一个半区进行查找；反之，如果此元素比要找的元素小，就在较大的一个半区进行查找。在每个更小的数据集中重复这个查找过程，直到找到要查找的元素或者数据集不能再分割。

图解

适用场景

二分查找可以应用于任何类型的数据，但前提是这些数据是按某种规则进行排序的。这使得它在处理那些频繁插入和删除操作的数据集时不太高效。因为执行完插入和删除操作后，无法保证数据集的有序性，在查找前还得先维护一个有序数据集，从而导致查找过程代价太高。此外，元素必须存储在连续的空间中。

因此，当待搜索的集合是相对静态的数据集时，此时使用二分查找是最好的选择。

代码示例（JS）

非递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var arr = [4, 9, 12, 13, 15, 33, 46, 49, 50, 77, 101];

function binary_search(arr, target) {
    var min = 0,
        max = arr.length;

    while (min <= max) {
        var mid = parseInt((min + max) / 2);

        if (target === arr[mid]) {
            return mid;
        } else if (target > arr[mid]) {
            min = mid + 1;
        } else {
            max = mid - 1;
        }
    }
    return -1;
}

console.log(binary_search(arr, 33));

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var arr = [4, 9, 12, 13, 15, 33, 46, 49, 50, 77, 101];

function binary_search(arr, min, max, target) {
    if (min > max) {
        return -1;
    }

    var mid = parseInt((min + max) / 2);

    if (target === arr[mid]) {
        return mid;
    } else if (target > arr[mid]) {
        min = mid + 1;
        return binary_search(arr, min, max, target);
    } else {
        max = mid - 1;
        return binary_search(arr, min, max, target);
    }
}

console.log(binary_search(arr, 0, arr.length - 1, 33));