共63道题，当前是第59题
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int MAXN = 100; 4 int arr[MAXN]; 5 bool BinarySearch(int n, int target){ 6 int left = 0, right = n - 1; 7 while (left <= right){ 8 int middle = (left + right) / 2; 9 if (arr[middle] < target) left = middle + 1; 10 else if (target < arr[middle]) 11 right = middle - 1; 12 else return true; 13 } 14 return false; 15 } 16 int main(){ 17 int n ,m; 18 cin >> n; 19 for (int i = 0; i < n; ++i) cin >> arr[i]; 20 sort(arr, arr + n); //(1)将arr数组中的元素从小到大排序 21 cin >> m; 22 for (int i = 0; i < m; ++i){ 23 int target; 24 cin >> target; 25 if (BinarySearch(n, target)) 26 cout << "YES" << endl; 27 else cout << "NO" << endl; 28 } 29 return 0; 30 }
1. T。代码显然是二分查找。
2. F。有 left == right 时恰好是关键字所在位置这一情况。
3. F。如果是从大到小排序，15 行和 17 行的两个 if 语句也要反过来。
4. A。考察位运算基本知识。
5. B。每次进循环第一次就找到，所以是总共 m 次。
6. C。查找序列中是否含有带查询元素。
该算法的时间复杂度是 $O(mlogn)$。（不考虑(1)的排序）（ ）
将 `while (left <= right)` 改成 `while(left < right)` ，其他地方不做改动，对程序最终的输出结果没有影响。（ ）
将 `sort(arr, arr + n);` 改成把 $arr$ 数组中的元素从大到小排序的代码，其他地方不做改动，对程序最终的输出结果没有影响。（ ）
将 `int middle = (left + right) / 2;` 改成下列选项中的哪一项，对于程序的运行没有影响。（ ）
若给定 $n$ 和 $arr$ 数组，在最好情况下，函数 $BinarySearch$ 中的 $while$ 循环需要被执行（ ）次。
若输入如下数据：
5
1 5 2 4 3
3
2 5 6
则输出结果为(用空格表示换行)：（ ）。