二分搜索是一种搜索算法，用于在已排序的数组中查找元素的位置。

在这种方法中，总是在数组一部分的中间搜索元素。

  1. 二分搜索只能在排序的项目列表上实现。如果元素尚未排序，我们需要先对它们进行排序。

算法的图解

二分搜索算法可以通过下面讨论的两种方式实现。

  1. 迭代法
  2. 递归法

递归方法遵循分而治之的方法。

下面讨论这两种方法的一般步骤：

  1. 要在其中执行搜索的数组是：
    设 x = 4 为要搜索的元素。 | 二分搜索（Binary Search） - 图1 | | —- | | 初始数组 |
  1. 分别在最低和最高位置设置两个指针低和高。 | 二分搜索（Binary Search） - 图2 | | —- | | 设置指针 |
  1. 找到数组的中间元素mid，即：arr[(low + high)/2] = 6 | 二分搜索（Binary Search） - 图3 | | —- | | 中间元素 |

  1. 如果 x == mid，则返回 mid.Else，将要搜索的元素与 m 进行比较。

  2. 如果 x > mid，则将 x 与 mid 右侧元素的中间元素进行比较。这是通过将低设置为低 = mid + 1 来完成的。

  3. 否则，将 x 与 mid 左侧元素的中间元素进行比较。这是通过将 high 设置为 high = mid - 1 来完成的。 | 二分搜索（Binary Search） - 图4 | | —- | | 寻找中间元素 |

  1. 重复步骤 3 到 6，直到低遇到高。 | 二分搜索（Binary Search） - 图5 | | —- | | 中间元素 |
  1. x = 4 被发现。 | 二分搜索（Binary Search） - 图6 | | —- | | 找到元素 |

算法的伪码

迭代法

  1. do until the pointers low and high meet each other.
  2.     mid = (low + high)/2
  3.     if (x == arr[mid])
  4.         return mid
  5.     else if (x > arr[mid]) // x is on the right side
  6.         low = mid + 1
  7.     else                       // x is on the left side
  8.         high = mid - 1

递归法

  1. binarySearch(arr, x, low, high)
  2.     if low > high
  3.         return False 
  4.     else
  5.         mid = (low + high) / 2 
  6.         if x == arr[mid]
  7.             return mid
  8.         else if x > arr[mid]        // x is on the right side
  9.             return binarySearch(arr, x, mid + 1, high)
  10.         else                               // x is on the right side
  11.             return binarySearch(arr, x, low, mid - 1)

算法的实现

迭代法

  1. // Binary Search in Java
  3. class BinarySearch {
  4.   int binarySearch(int array[], int x, int low, int high) {
  6.     // Repeat until the pointers low and high meet each other
  7.     while (low <= high) {
  8.       int mid = low + (high - low) / 2;
  10.       if (array[mid] == x)
  11.         return mid;
  13.       if (array[mid] < x)
  14.         low = mid + 1;
  16.       else
  17.         high = mid - 1;
  18.     }
  20.     return -1;
  21.   }
  23.   public static void main(String args[]) {
  24.     BinarySearch ob = new BinarySearch();
  25.     int array[] = { 3, 4, 5, 6, 7, 8, 9 };
  26.     int n = array.length;
  27.     int x = 4;
  28.     int result = ob.binarySearch(array, x, 0, n - 1);
  29.     if (result == -1)
  30.       System.out.println("Not found");
  31.     else
  32.       System.out.println("Element found at index " + result);
  33.   }
  34. }

递归法

  1. // Binary Search in Java
  3. class BinarySearch {
  4.   int binarySearch(int array[], int x, int low, int high) {
  6.     if (high >= low) {
  7.       int mid = low + (high - low) / 2;
  9.       // If found at mid, then return it
  10.       if (array[mid] == x)
  11.         return mid;
  13.       // Search the left half
  14.       if (array[mid] > x)
  15.         return binarySearch(array, x, low, mid - 1);
  17.       // Search the right half
  18.       return binarySearch(array, x, mid + 1, high);
  19.     }
  21.     return -1;
  22.   }
  24.   public static void main(String args[]) {
  25.     BinarySearch ob = new BinarySearch();
  26.     int array[] = { 3, 4, 5, 6, 7, 8, 9 };
  27.     int n = array.length;
  28.     int x = 4;
  29.     int result = ob.binarySearch(array, x, 0, n - 1);
  30.     if (result == -1)
  31.       System.out.println("Not found");
  32.     else
  33.       System.out.println("Element found at index " + result);
  34.   }
  35. }

算法复杂度

  • 时间复杂度

    • 最佳情况复杂度：O(1)
    • 平均案例复杂度：O(log n)
    • 最坏情况复杂度：O(log n)

  • 空间复杂度

    • 二分查找的空间复杂度为O(1)。

算法的应用

  • 在 Java、.Net、C++ STL 库中
  • 在调试时，二分查找用于查明错误发生的位置。