二分查找

Posted on Edited on In

题目描述
二分查找是一种在有序数组中查找特定元素的高效算法。它的基本思想是将目标值与数组中间的元素进行比较，如果相等则找到目标；如果目标值小于中间元素，则在左半部分继续查找；如果目标值大于中间元素，则在右半部分继续查找。重复这个过程，直到找到目标值或者确定目标值不存在。

输入格式
输入共 3 行，第一行是一个整数 n，表示数组的长度。第二行包含 n 个整数，表示已经排序好的数组（升序）。第三行是一个整数 x，表示要查找的目标值。

输出格式
输出共 1 行，如果找到目标值 x，则输出其在数组中的下标（从0开始计数）；如果不存在，则输出 -1。如果数组中存在多个相同的 x，输出任意一个即可。

数据范围
1 ≤ n ≤ 100000
-1000000 ≤ 数组元素, x ≤ 1000000

输入样例1：

1
2
3
10
1 3 5 7 9 11 13 15 17 19
7

输出样例1：

1
3

输入样例2：

1
2
3
10
1 3 5 7 9 11 13 15 17 19
6

输出样例2：

1
-1

注意事项

  • 二分查找的时间复杂度为 O(logn)，空间复杂度为 O(1)。
  • 二分查找要求数组必须是有序的。
  • 当处理大规模数据时，二分查找比线性查找更高效。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
using namespace std;

// 二分查找函数（递归实现）
int binarySearchRecursive(int a[], int left, int right, int x)
{
    if (left > right)
    {
        return -1; // 未找到目标值
    }
    
    int mid = left + (right - left) / 2; // 计算中间位置，避免整数溢出
    
    if (a[mid] == x)
    {
        return mid; // 找到目标值
    }
    else if (a[mid] > x)
    {
        return binarySearchRecursive(a, left, mid - 1, x); // 在左半部分查找
    }
    else
    {
        return binarySearchRecursive(a, mid + 1, right, x); // 在右半部分查找
    }
}

// 二分查找函数（非递归实现）
int binarySearchIterative(int a[], int n, int x)
{
    int left = 0;
    int right = n - 1;
    
    while (left <= right)
    {
        int mid = left + (right - left) / 2; // 计算中间位置，避免整数溢出
        
        if (a[mid] == x)
        {
            return mid; // 找到目标值
        }
        else if (a[mid] > x)
        {
            right = mid - 1; // 在左半部分查找
        }
        else
        {
            left = mid + 1; // 在右半部分查找
        }
    }
    
    return -1; // 未找到目标值
}

int main()
{
    int n;
    cin >> n;
    int a[n];
    
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    
    int x;
    cin >> x;
    
    // 调用非递归版本的二分查找函数
    int result = binarySearchIterative(a, n, x);
    
    // 如果要使用递归版本，可以取消下面这行的注释，并注释掉上面这行
    // int result = binarySearchRecursive(a, 0, n - 1, x);
    
    cout << result << endl;
    
    return 0;
}

时间复杂度

  • 时间复杂度：O(logn)，其中 n 为数组的长度。
  • 空间复杂度：O(1)（非递归实现）或 O(logn)（递归实现，由递归调用栈占用的空间）。

代码解释

  • 二分查找的核心思想是将目标值与数组中间的元素进行比较，并根据比较结果缩小查找范围。
  • 在这个实现中，我们提供了两种版本的二分查找：递归版本和非递归版本。
  • 递归版本的终止条件是左边界大于右边界（表示未找到目标值）或者找到目标值。
  • 非递归版本使用循环来代替递归，循环的条件是左边界小于等于右边界。
  • 在计算中间位置时，我们使用 mid = left + (right - left) / 2 而不是 mid = (left + right) / 2，这是为了避免在 left 和 right 很大时发生整数溢出。