跳到主要内容

二分搜索

提示
  1. 二分查找特点：二分查找是一种高效的查找算法，用于在已排序数组中查找特定元素，通过将搜索区间分为两半来减少搜索时间。
  2. 实现方法：二分查找可以通过迭代或递归方法实现，其中迭代方法直到两个指针相遇，而递归方法遵循分而治之的策略。
  3. 应用场景：二分查找广泛应用于各种编程语言的库中，以及在调试过程中精确定位错误发生的位置。

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

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

二分查找只能在已排序的元素列表上实现。如果元素尚未排序，我们首先需要对它们进行排序。

二分查找的工作原理​

二分查找算法可以通过以下两种方式实现，具体如下所述。

  1. 迭代方法
  2. 递归方法

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

下面讨论了这两种方法的通用步骤。

  1. 要进行搜索的数组是： 初始数组 二分查找

    假设要搜索的元素 x = 4。

  2. 分别在最低和最高位置设置两个指针 low 和 high。 设置指针 二分查找

  3. 找到数组的中间元素 mid，即 arr[(low + high)/2] = 6。 中间元素 二分查找

  4. 如果 x == mid，则返回 mid。否则，将要搜索的元素与 m 比较。

  5. 如果 x > mid，将 x 与 mid 右侧元素的中间元素比较。通过设置 low = mid + 1 来完成。

  6. 否则，将 x 与 mid 左侧元素的中间元素比较。通过设置 high = mid - 1 来完成。 找到中间元素 二分查找

  7. 重复步骤 3 到 6，直到 low 与 high 相遇。 中间元素 二分查找

  8. 找到了 x = 4。 找到 二分查找

二分查找算法​

迭代方法​

直到指针 low 和 high 相遇为止。


    mid = (low + high)/2
    if (x == arr[mid])
        return mid
    else if (x > arr[mid]) // x 在右侧
        low = mid + 1
    else                       // x 在左侧
        high = mid - 1

递归方法​

binarySearch(arr, x, low, high)
    if low > high
        return False
    else
        mid = (low + high) / 2
        if x == arr[mid]
            return mid
        else if x > arr[mid]        // x 在右侧
            return binarySearch(arr, x, mid + 1, high)
        else                               // x 在左侧
            return binarySearch(arr, x, low, mid - 1)

Python、Java、C/C++ 示例（迭代方法）​

Python Java C C++

# Python 中的二分查找


def binarySearch(array, x, low, high):

    # 重复直到指针 low 和 high 相遇
    while low <= high:

        mid = low + (high - low)//2

        if array[mid] == x:
            return mid

        elif array[mid] < x:
            low = mid + 1

        else:
            high = mid - 1

    return -1


array = [3, 4, 5, 6, 7, 8, 9]
x = 4

result = binarySearch(array, x, 0, len(array)-1)

if result != -1:
    print("元素在索引 " + str(result) + " 处找到")
else:
    print("未找到")
// Java 中的二分查找

class BinarySearch {
  int binarySearch(int array[], int x, int low, int high) {

    // 重复操作直到 low 和 high 指针相遇
    while (low <= high) {
      int mid = low + (high - low) / 2;

      if (array[mid] == x)
        return mid;

      if (array[mid] < x)
        low = mid + 1;

      else
        high = mid - 1;
    }

    return -1;
  }

  public static void main(String args[]) {
    BinarySearch ob = new BinarySearch();
    int array[] = { 3, 4, 5, 6, 7, 8, 9 };
    int n = array.length;
    int x = 4;
    int result = ob.binarySearch(array, x, 0, n - 1);
    if (result == -1)
      System.out.println("未找到");
    else
      System.out.println("元素位于索引 " + result);
  }
}
// C 中的二分查找

#include <stdio.h>

int binarySearch(int array[], int x, int low, int high) {
  // 重复操作直到 low 和 high 指针相遇
  while (low <= high) {
    int mid = low + (high - low) / 2;

    if (array[mid] == x)
      return mid;

    if (array[mid] < x)
      low = mid + 1;

    else
      high = mid - 1;
  }

  return -1;
}

int main(void) {
  int array[] = {3, 4, 5, 6, 7, 8, 9};
  int n = sizeof(array) / sizeof(array[0]);
  int x = 4;
  int result = binarySearch(array, x, 0, n - 1);
  if (result == -1)
    printf("未找到");
  else
    printf("元素位于索引 %d", result);
  return 0;
}
// C++ 中的二分查找

#include <iostream>
using namespace std;

int binarySearch(int array[], int x, int low, int high) {

	// 重复操作直到 low 和 high 指针相遇
  while (low <= high) {
    int mid = low + (high - low) / 2;

    if (array[mid] == x)
      return mid;

    if (array[mid] < x)
      low = mid + 1;

    else
      high = mid - 1;
  }

  return -1;
}

int main(void) {
  int array[] = {3, 4, 5, 6, 7, 8, 9};
  int x = 4;
  int n = sizeof(array) / sizeof(array[0]);
  int result = binarySearch(array, x, 0, n - 1);
  if (result == -1)
    printf("未找到");
  else
    printf("元素位于索引 %d", result);
}

Python、Java、C/C++ 示例（递归方法）​

Python Java C C++

# Python 中的二分查找


def binarySearch(array, x, low, high):

    if high >= low:

        mid = low + (high - low)//2

        # 如果在中间找到，则返回它
        if array[mid] == x:
            return mid

        # 搜索左半边
        elif array[mid] > x:
            return binarySearch(array, x, low, mid-1)

        # 搜索右半边
        else:
            return binarySearch(array, x, mid + 1, high)

    else:
        return -1


array = [3, 4, 5, 6, 7, 8, 9]
x = 4

result = binarySearch(array, x, 0, len(array)-1)

if result != -1:
    print("元素位于索引 " + str(result))
else:
    print("未找到")
// Java 中的二分查找

class BinarySearch {
  int binarySearch(int array[], int x, int low, int high) {

    if (high >= low) {
      int mid = low + (high - low) / 2;

      // 如果在中间找到，则返回它
      if (array[mid] == x)
        return mid;

      // 搜索左半边
      if (array[mid] > x)
        return binarySearch(array, x, low, mid - 1);

      // 搜索右半边
      return binarySearch(array, x, mid + 1, high);
    }

    return -1;
  }

  public static void main(String args[]) {
    BinarySearch ob = new BinarySearch();
    int array[] = { 3, 4, 5, 6, 7, 8, 9 };
    int n = array.length;
    int x = 4;
    int result = ob.binarySearch(array, x, 0, n - 1);
    if (result == -1)
      System.out.println("未找到");
    else
      System.out.println("元素位于索引 " + result);
  }
}
// C 中的二分查找

#include <stdio.h>

int binarySearch(int array[], int x, int low, int high) {
  if (high >= low) {
    int mid = low + (high - low) / 2;

    // 如果在中间找到，则返回它
    if (array[mid] == x)
      return mid;

    // 搜索左半边
    if (array[mid] > x)
      return binarySearch(array, x, low, mid - 1);

    // 搜索右半边
    return binarySearch(array, x, mid + 1, high);
  }

  return -1;
}

int main(void) {
  int array[] = {3, 4, 5, 6, 7, 8, 9};
  int n = sizeof(array) / sizeof(array[0]);
  int x = 4;
  int result = binarySearch(array, x, 0, n - 1);
  if (result == -1)
    printf("未找到");
  else
    printf("元素位于索引 %d", result);
}
// C++ 中的二分查找

#include <iostream>
using namespace std;

int binarySearch(int array[], int x, int low, int high) {
  if (high >= low) {
    int mid = low + (high - low) / 2;

    // 如果在中间找到，返回其位置
    if (array[mid] == x)
      return mid;

    // 搜索左半边
    if (array[mid] > x)
      return binarySearch(array, x, low, mid - 1);

    // 搜索右半边
    return binarySearch(array, x, mid + 1, high);
  }

  return -1;
}

int main(void) {
  int array[] = {3, 4, 5, 6, 7, 8, 9};
  int x = 4;
  int n = sizeof(array) / sizeof(array[0]);
  int result = binarySearch(array, x, 0, n - 1);
  if (result == -1)
    printf("未找到");
  else
    printf("元素位于索引 %d", result);
}

二分查找的复杂度​

时间复杂度

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

空间复杂度

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

二分查找的应用​

  • 在 Java、.Net、C++ STL 的库中
  • 在调试时，二分查找用于精确定位错误发生的位置。
最后于 更新