完善程序（三）- 切割

题目描述

（切割） 将一个单调递增的数组从某一位置切成两半，然后交换左半边和右半边。现在给出交换后的数组，多次询问，每次给出一个元素 k，问数组中是否存在该元素。

提示： 先使用二分查找，找到切割点，则切割点左边的数组单调递增，右边的数组单调递增，再对半边数组进行二分查找，寻找元素 k。

#include <iostream>
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn];
bool binary_search(int l, int r, int k) { // 用于实现二分查找，判断 [l,r] 中是否有 k 出现
    while(【1】) {
        int mid = (l + r) >> 1;
        if(a[mid] == k) {
            【2】;
        } else if(a[mid] > k) {
            r = mid;
        } else {
            l = mid;
        }
    }
    return a[l] == k || a[r] == k;
}
int main() {
    int n, m, k;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int L = 1, R = n, pos;
    while(L <= R) {
        int mid = (L + R) / 2;
        if(【3】) {
            L = mid + 1;
            pos = mid;
        } else {
            R = mid - 1;
        }
    }
    cin >> m; // 表示共有 m 次询问
    while(m--) {
        cin >> k;
        if(k >= a[1]) {
            if(【4】)    cout << "YES" << endl;
            else    cout << "NO" << endl;
        } else {
            if(【5】)    cout << "YES" << endl;
            else    cout << "NO" << endl;
        }
    }
}

第 1 题（20 分） 1 处应填：{{ select(1) }}

• A. l <= r
• B. l < r
• C. l + 1 < r
• D. l >= r

第 2 题（20 分） 2 处应填：{{ select(2) }}

• A. break
• B. return true
• C. l = mid + 1
• D. r = mid - 1

第 3 题（20 分） 3 处应填：{{ select(3) }}

• A. a[mid] > k
• B. mid > k
• C. a[mid] >= a[1]
• D. a[mid] > a[1]

第 4 题（20 分） 4 处应填：{{ select(4) }}

• A. binary_search(L, R, k)
• B. binary_search(1, pos+1, k)
• C. binary_search(L, pos, k)
• D. binary_search(1, pos, k)

第 5 题（20 分） 5 处应填：{{ select(5) }}

• A. binary_search(pos, R, k)
• B. binary_search(pos+1, R, k)
• C. binary_search(pos+1, n, k)
• D. binary_search(L, R, k)