E. Binary Search

题目链接：Problem - E - Codeforces

题目大意：

初始时有 l=1,r=n+1。

1. 如果当前 r−l=1，退出二分查找，并且认定 l为二分查找的结果。
2. 定义 m=⌊2l+r​⌋。
3. 如果 m≤x，将 l 赋值为 m，否则将 r 赋值为 m。

不断重复以上三个操作直到得到结果。

显然当 p 未排序时二分查找的结果不一定为 x，现在你希望进行不超过两次交换操作，使得操作后的排列 p 能使得二分查找的结果为 x。

一次交换操作为：选择 1≤i,j≤n，交换 pi,pj​。

你需要给出交换的参数，容易证明两次操作总是足够的。

考察内容： 二分， 构造

解题思路：首先先按照题目要求写出二分模板代码，进行二分，如题目要求所说l认定为二分答案，检查最后的a[l]是否为x, 然后构造：当发现a[l]是x时，输出0即可， 不是就将ans的下标与l进行交换。 所以最多进行一次的交换。

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using i128 = __int128;

void solve(){
    int n, x;
    cin >> n >> x;
    vector<int> a(n+1);
    int pos = 0;
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        if(a[i]==x) {//记录ans的位置
            pos = i;
        }
    }
    int l = 1, r = n+1;
    while(l+1 < r) {
        int mid = (l+r)>>1;
        if(a[mid] <= x) {
            l = mid;
        }else{
            r = mid;
        }
    }  //题目要求的二分板子  
    if(a[l] == x) {
        cout << 0 << "\n";
    }else{
        cout << 1 << "\n"; //找不到让最后的位置变为ans即可
        cout << l << " " << pos << "\n";
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

欢迎大佬指正。