首页 > 编程笔记 > C++笔记

二分搜索算法（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，表示该值没有出现在数组中。
  1. int binarySearch(const int array[], int size, int value)
  2. {
  3.     int first = 0, //第一个数组元素
  4.     last = size - 1, //最后一个数组元素
  5.     middle, //搜索的中点
  6.     position = -1; //搜索值的位置
  7.     bool found = false; // 标记
  8.     while (!found && first <= last)
  9.     {
  10.         middle = (first + last) / 2; // 计算中点
  11.         if (array[middle] == value) // 如果在中点发现值
  12.         {
  13.             found = true;
  14.             position = middle;
  15.         }
  16.         else if (array [middle] > value) // 如果值在下半部分
  17.             last = middle - 1;
  18.         else
  19.             first = middle + 1; //如果值在上半部分
  20.     }
  21.     return position;
  22. }
下面的程序是一个使用 binarySearch 函数的完整程序。它将搜索一个包含员工 ID 号的数组，以查找特定的值。 
  1. //This program performs a binary search on an integer array whose elements are in ascending order.
  2. #include <iostream>
  3. using namespace std;
  4.  
  5. //Function prototype
  6.  
  7. int binarySearch(const int [], int, int);
  8. const int SIZE = 20;
  9. int main()
  10. {
  11.     // Create an array of ID numbers sorted in ascending order
  12.     int IDnums[SIZE] = {101, 142, 147, 189, 199, 207, 222,234, 289, 296, 310, 319, 388, 394, 417, 429, 447, 521, 536, 600 };
  13.     int empID, // Holds the ID to search for
  14.     results;//Holds the search results
  15.     // Get an employee ID to search for
  16.     cout << "Enter the employee ID you wish to search for: ";
  17.     cin >> empID;
  18.     // Search for the ID
  19.     results = binarySearch(IDnums, SIZE, empID);
  20.     // If binarySearch returned -1, the ID was not found
  21.     if (results == -1)
  22.         cout << "That number does not exist in the array.\n";
  23.     else
  24.     {
  25.         // Otherwise results contains the subscript of
  26.         // the specified employee ID in the array
  27.         cout << "ID " << empID << " was found in element " << results << " of the array.\n";
  28.     }
  29.     return 0;
  30. }
  31.  
  32. int binarySearch(const int array[], int size, int value)
  33. {
  34.     int first = 0, // First array element
  35.     last = size - 1, // Last array element
  36.     middle,    // Midpoint of search
  37.     position = -1; // Position of search value
  38.     bool found = false; // Flag
  39.     while (!found && first <= last)
  40.     {   
  41.         middle = (first + last) / 2; // Calculate midpoint
  42.         if (array[middle] == value) // If value is found at mid
  43.         {
  44.             found = true;
  45.             position = middle;
  46.         }
  47.         else if (array[middle] > value) // If value is in lower half
  48.             last = middle - 1;
  49.         else
  50.             first = middle +1; // If value is in upper half
  51.     }
  52.     return position;
  53. }
程序输出结果：

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。