利用二分查找找出所给出的数在数组中的下标

输入格式：

第一行输入n和m表示数组有n个数据，m表示要对m个数进行查找

输出格式：

所有输出在一行完成，行末没有多余空格和多余回车。

输入样例：

1
2
3
5 5
1 2 3 4 5
1 2 3 4 5

输出样例：

1
0 1 2 3 4

思路

一道二分查找的模板题

查找不用多说，大部分情况为在数组中寻找某个数，最简单的方法就是遍历一遍，复杂度O(n)

二分查找要求数组有序，核心思想如下：（假设待查找数据为data）

  1. 若data大于数组中间位置的值，则data出现在数组后半部分
  2. 若data小于数组中间位置的值，则data出现在数组前半部分

依据以上规则，不断比较data和查找范围数组中间的值。二分查找复杂度为O(logn)

如此一想，可以衍生出三分、四分。。。

知识点：二分查找（很重要，这是一种思想，属于面试题常备军）

代码

代码为递归形式，初学便于理解，其实迭代使用的更多。该题解复杂度为O(mlogn)

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
#include <iostream>
#include <vector>

using namespace std;

/**
* 其实该题有些不严谨
* 没有说明数据范围，而且PTA上显示出现了问题（因为md语法错了）
*/

int mybinary_find(const vector<int> &ve, int left, int right, int data) {//引用提高效率，否则超时
    if(left > right) {//递归函数出口
        return -1;
    }
    int mid = left + (right - left) / 2;//计算中间位置的索引（right+left）/2，这样写是为了防止right+left越界
    if(ve[mid] == data) {//找到了
        return mid;
    } else if(ve[mid] < data) {//数据在中间的右边
        return mybinary_find(ve, mid + 1, right, data);//去右边找
    } else {//数据在中间的左边
        return mybinary_find(ve, left, mid - 1, data);//去左边找
    }
}

int main() {
    int m, n;
    scanf("%d %d", &n, &m);//使用cin会超时
    vector<int> ve;
    for(int i = 1; i <= n; i++) {
        int id;
        scanf("%d", &id);
        ve.push_back(id);
    }
    for(int i = 1; i <= m; i++) {
        int id;
        scanf("%d", &id);
        printf("%d", mybinary_find(ve, 0, n - 1, id));
        printf("%c", i == m ? '\n' : ' ');
    }
    return 0;
}

其实，如果不考虑题目要求，可以标记查找（哈希查找），复杂度O(m)，更快

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
    int m, n;
    scanf("%d %d", &n, &m);//使用cin会超时
    unordered_map<int, int> book; //记录某个数出现的位置，默认为0
    for(int i = 1; i <= n; i++) {
        int id;
        scanf("%d", &id);
        book[id] = i;
    }
    for(int i = 1; i <= m; i++) {
        int id;
        scanf("%d", &id);
        printf("%d", book[id] - 1);
        printf("%c", i == m ? '\n' : ' ');
    }
    return 0;
}