二分搜索算法（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 次比较，因为 2¹⁶ = 65 536；要在包含 1 000 000 个元素的数组中查找某个特定的项目，则最多只需要进行 20 次比较，因为 2²⁰= 1 048 576。