共48道题，当前是第32题

初赛真题

01 #include<iostream>
02 #include<cstdio>
03 
04 using namespace std;
05 
06 const int MAXN = 100;
07 
08 int arr[MAXN] ;
09 
10 bool BinarySearch(int n, int target) {
11     int left = 0;
12     int right = n- 1;
13     while (left <= right) {
14         int middle = (left + right) / 2;
15         if (arr[middle] < target) {
16             left = middle + 1;
17         } else if (target < arr[middle]) {
18             right = middle- 1;
19         } else {
20             return true;
21         }
22     }
23     return false;
24 }
25 
26 int main() {
27     int n，m;
28     cin >> n
29     for(int i = 0; i < n; i++)
30         cin >> arr[i];
31     sort(arr, arr + n); //将arr数组中的元素从小到大排序
32     cin >> m;
33     for(int i = 0; i < m; i++){
34         int target;
35         cin >> target;
36         if (BinarySearch(n, target)) {
37             cout << "YES" << endl;
38         } else {
39             cout << "NO" << endl;
40         }
41     }
42     return 0;
43 }

1. A。代码显然是二分查找。
2. B。有 left == right 时恰好是关键字所在位置这一情况。
3. A。正整数运算右移一位相当于除以 $2$ 取整。
4. B。如果是从大到小排序，$15$ 行和 $17$ 行的两个 if 语句也要反过来。
5. B。每次进循环第一次就找到，所以是总共 $m$ 次。
6. C。查找序列中是否含有带查询元素。

Question

1. 该算法的时间复杂度是 $O(mlogn)$。(不考虑第 31 行的排序) ()

2. 将第 13 行的代码改成 while(left < right) ，其他地方不做改动，对程序最终的输出结果没有影响。()

3. 将第 14 行的代码改成 int middle = (left + right) >> 1，其他地方不做改动，对程序最终的输出结果没有影响。()

4. 将第 31 行代码改成把 arr 数组中的元素从大到小排序的代码，其他地方不做改动，对程序最终的输出结果没有影响。()

5. 若给定 n 和 arr 数组，在最好情况下，13 行至 22 行的 while 循环需要被执行()次

6. 若输入如下数据:
5
1 5 2 4 3
3
2 5 6
则输出结果为(用空格表示换行): () 。