二分搜索

简介：

在计算机科学中，二分搜索（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是一种在 有序 数组中查找某一特定元素的搜索算法。

所要查找的对象，必须在一个 单调递增/递减 的数组或其他可比较的数据结构中。

性能：

时间复杂度：O(logn)

空间复杂度：

  • 非递归 O(1)

  • 递归 O(logn)

原理&过程：

代码实现:

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
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int Binarr_Search(int arr[], int arr_size, int target)
{
    int low = 0;
    int high = arr_size - 1;
    int mid;

    while(low <= high)
    {
        mid = (low + high) / 2;

        if(target < arr[mid])
        {
            high = mid - 1;
        }
        else if (arr[mid] < target)
        {
            low = mid + 1;
        }
        else 
        {
            return mid;
        }
    }

    //如果需要找第一个大于等于 target 的数时，需要将返回结果改为：
    return low;
    
    //如果对于找不到的查询返回 -1 ，需要将返回结果改为：
    //return -1;
}

int main()
{
    int arr[10] = {0, 2, 4, 6, 8, 10, 12, 14, 16, 18};
    int arr_size = 10;
    
    int target;
    int ans;

    cin >> target;

    ans = Binarr_Search(arr, arr_size, target);

    cout << ans << endl;

    return 0;
}

在 C++ STL 中已经存在了一套直接可以用的二分查找函数，感觉还可以，在这里把网上的资料总结一下。

1. 头文件

1
#include <algorithm>

2. 常用操作

<1> 查找某个元素是否出现。

  • 函数模板：binary_search(arr[], arr[]+size, indx);

  • 参数说明：

    • arr[]： 数组首地址
    • size：数组元素个数
    • indx：需要查找的值

  • 函数功能： 在数组中以二分法检索的方式查找，若在数组(要求数组元素非递减)中查找到 indx 元素则返回 1，若查找不到则返回 0 。

<2> 查找第一个大于或等于某个元素的位置。

  • 函数模板：lower_bound(arr[], arr[]+size , indx);

  • 参数说明：

    • arr[]： 数组首地址
    • size：数组元素个数
    • indx：需要查找的值

  • 函数功能： 返回大于或等于 indx 的第一个元素位置(注意是地址)，如果需要下标需要 - arr[]。如果所有元素都小于 indx ，则返回 最后一个下标 + 1 （注意：这时数组下标越界）。

<3>查找第一个大于某个元素的位置。

  • 函数模板：upper_bound(arr[], arr[]+size, indx);
  • 参数说明：
    • arr[]： 数组首地址
    • size：数组元素个数
    • indx：需要查找的值
  • 函数功能： 返回大于 indx 的第一个元素位置(注意是地址)，如果需要下标需要 - arr[]。如果所有元素都小于 indx ，则返回 最后一个下标 + 1 （注意：这时数组下标越界）。

<4>代码实例：

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
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int a[100] = {4, 10, 11, 30, 69, 70, 96, 100};

    int b = binary_search(a, a + 9, 4); //查找成功，返回1s
    cout << "在数组中查找元素4，结果为：" << b << endl;
    // 在数组中查找元素4，结果为：1

    int c = binary_search(a, a + 9, 40); //查找失败，返回0
    cout << "在数组中查找元素40，结果为：" << c << endl;
    // 在数组中查找元素40，结果为：0

    int d = lower_bound(a, a + 9, 10) - a;
    cout << "在数组中查找第一个大于等于10的元素位置，结果为：" << d << endl;
    // 在数组中查找第一个大于等于10的元素位置，结果为：1

    int e = lower_bound(a, a + 9, 101) - a;
    cout << "在数组中查找第一个大于等于101的元素位置，结果为：" << e << endl;
    // 在数组中查找第一个大于等于101的元素位置，结果为：9

    int f = upper_bound(a, a + 9, 10) - a;
    cout << "在数组中查找第一个大于10的元素位置，结果为：" << f << endl;
    // 在数组中查找第一个大于10的元素位置，结果为：2

    int g = upper_bound(a, a + 9, 101) - a;
    cout << "在数组中查找第一个大于101的元素位置，结果为：" << g << endl;
    // 在数组中查找第一个大于101的元素位置，结果为：9

    return 0;
}

实用代码：

实际开发过程中，用来存放数据的为 vector 这种数据结构，并且二分其实也有一套成熟的函数来进行调用。

以下是针对 vector 和 二分库中的函数调用 实现代码：

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//查找第一个大于或等于某个元素的位置
int Binary_Search(vector<int> &nums, int target)
{
    sort(nums.begin(), nums.end());

    return lower_bound(nums.begin(), nums.end(), target) - nums.begin();
}

int main()
{
    vector<int> nums;
    
    int num;
    int len;

    cin >> len;

    for (int i = 0; i < len; ++i)
    {
        cin >> num;
        nums.push_back(num);
    }

    int target;

    cin >> target;
    cout << Binary_Search(nums, target) << endl;

    return 0;
}

参考资料：

https://www.cnblogs.com/wkfvawl/p/9475939.html