二分搜索算法(C++详解版)

二分搜索(Binary Search)是一种比线性搜索更有效的巧妙算法。它唯一的要求是数组中的值是有序的。

二分搜索算法测试数组不是从第一个元素开始,而是从中间的元素开始。如果该元素碰巧包含所需的值,则搜索结束。否则,中间元素的值要么大于要么小于正在搜索的值。如果它大于期望值,那么该值(如果它在列表中)将在数组的前半部分中找到;如果它小于期望值,那么该值(同样需要假设它在列表中)将在数组的后半部分中找到。在任何一种情况下,数组元素的一半就已经从进一步搜索范围中排除。

如果在中间元素中找不到所需的值,那么对于可能包含该值的一半数组,将重复该过程。例如,如果要搜索数组的后半部分,算法立即测试其中间元素。如果没有找到所需的值,那么搜索范围将缩小到该元素之前或之后的数组的四分之一。这个过程一直持续到被查找的值被找到,或者没有更多的元素要测试。

下面是一个函数的伪代码,它可以对以升序存储元素的数组执行二分搜索:
Set first to 0
Set last to the last subscript in the array
Set found to false
Set position to -1
While found is not true and first is less than or equal to last
    Set middle to the subscript halfway between first and last
    If array[middle] equals the desired value
        Set found to true
        Set position to middle
    Else If array[middle] is greater than the desired value
        Set last to middle - 1
    Else
        Set first to middle + 1
    End If
End While
Return position
该算法使用 3 个索引变量:first、last 和 middle。first 和 last 变量标记当前正在搜索的数组部分的边界。它们用数组的第一个和最后一个元素的下标进行初始化。middle 则是在 first 和 last 元素之间大约中点位置的元素的下标,该值的计算方法就是釆用 first 和 last 相加求和然后除以 2,结果将被存储在 middle 变量中。

如果没有精确的中心元素,则使用整除法计算 middle 值,选择紧邻中点的元素。如果数组中间的元素不包含搜索值,则调整 first 或 last 变量,以便在下一次迭代期间只搜索数组的顶部或底部的一半。每次循环无法搜索到值时,都会将正在搜索的数组部分切割成一半。

以下 C++ 示例代码中的 binarySearch 函数将用于在整数数组上执行二分搜索。第一个形参 array,其元素的个数为 size,以下语句将搜索它是否出现了存储在 value 中的数字。如果找到该数字,则返回其数组下标。否则,返回 -1,表示该值没有出现在数组中。
int binarySearch(const int array[], int size, int value)
{
    int first = 0, //第一个数组元素
    last = size - 1, //最后一个数组元素
    middle, //搜索的中点
    position = -1; //搜索值的位置
    bool found = false; // 标记
    while (!found && first <= last)
    {
        middle = (first + last) / 2; // 计算中点
        if (array[middle] == value) // 如果在中点发现值
        {
            found = true;
            position = middle;
        }
        else if (array [middle] > value) // 如果值在下半部分
            last = middle - 1;
        else
            first = middle + 1; //如果值在上半部分
    }
    return position;
}
下面的程序是一个使用 binarySearch 函数的完整程序。它将搜索一个包含员工 ID 号的数组,以查找特定的值。
//This program performs a binary search on an integer array whose elements are in ascending order.
#include <iostream>
using namespace std;

//Function prototype

int binarySearch(const int [], int, int);
const int SIZE = 20;
int main()
{
    // Create an array of ID numbers sorted in ascending order
    int IDnums[SIZE] = {101, 142, 147, 189, 199, 207, 222,234, 289, 296, 310, 319, 388, 394, 417, 429, 447, 521, 536, 600 };
    int empID, // Holds the ID to search for
    results;//Holds the search results
    // Get an employee ID to search for
    cout << "Enter the employee ID you wish to search for: ";
    cin >> empID;
    // Search for the ID
    results = binarySearch(IDnums, SIZE, empID);
    // If binarySearch returned -1, the ID was not found
    if (results == -1)
        cout << "That number does not exist in the array.\n";
    else
    {
        // Otherwise results contains the subscript of
        // the specified employee ID in the array
        cout << "ID " << empID << " was found in element " << results << " of the array.\n";
    }
    return 0;
}

int binarySearch(const int array[], int size, int value)
{
    int first = 0, // First array element
    last = size - 1, // Last array element
    middle,    // Midpoint of search
    position = -1; // Position of search value
    bool found = false; // Flag
    while (!found && first <= last)
    {   
        middle = (first + last) / 2; // Calculate midpoint
        if (array[middle] == value) // If value is found at mid
        {
            found = true;
            position = middle;
        }
        else if (array[middle] > value) // If value is in lower half
            last = middle - 1;
        else
            first = middle +1; // If value is in upper half
    }
    return position;
}
程序输出结果:

Enter the employee ID you wish to search for: 199
ID 199 was found in element 4 of the array.

二分搜索的效率

显然,二分搜索比线性搜索更有效率。每次进行比较,找不到所需的项目时,都会剔除必须搜索的数组剩余部分的一半。

例如,考虑有 20 000 个元素的数组。如果二分搜索未能在第一次尝试中找到某个项目,则剩余要搜索的元素数量为 10 000。如果在第二次尝试中未找到该项目,则仍然要搜索的元素的数量是 5000。这个过程一直持续到二分搜索找到所需的值或者确定它不在数组中。如果在数组中有 20 000 个元素,那么这最多需要 15 次比较。如果使用线性搜索的话,则平均需要进行 10 000 次比较,所以二分搜索的效率高太多了。

可以使用 2 的幂值来计算二分搜索在任何大小的数组上进行比较的最大次数。2 的幂值就是以 2 为底数的整数指数幂。只要找出大于数组中元素个数的 2 的最小幂值,即可知道查找一个元素所需的最大比较次数,或者确定它不存在。

例如,要在包含 50 000 个元素的数组中查找某个特定的项目,则最多只需要进行 16 次比较,因为 216 = 65 536;要在包含 1 000 000 个元素的数组中查找某个特定的项目,则最多只需要进行 20 次比较,因为 220= 1 048 576。