Description

給你一個字符串str，字符串中的字母都已按照升序排序，且只包含小寫字母。另外給出一個目標字母target，請你尋找在這一有序字符串里比目標字母大的最小字母。
在比較時，字母是依序循環出現的。例如，str=“ab”，target=‘z’，則答案為’a’。
字符串str至少包含了兩個不同的字母。
target是一個小寫字母。
要求必須使用二分查找來解題。

Input

第一行輸入t，表示有t個測試樣例。
第二行起，每一行首先輸入一個字符串str，接著輸入目標字母target。
以此類推共輸入t個測試樣例。
接收字符串可以使用：#include ，string str; cin>>str;

Output

每一行輸出字符串中比目標字母大的最小字母。
以此類推共輸出t行。

Sample

#0

Input

7
abcd a
abcd b
acegi r
abce c
aaaabbbbbccc b
aaaaabbbbbccccceeeee c
aaabbcccddd z

Output

b
c
a
e
c
e
a

Hint

2 <= str.length() <= 10000000

解題思路

需要考慮的細節是二分查找后如果壓縮出來的這個字母仍然比target小怎么辦？
則說明此時已經查找到了字符串中的最后一個字母（下標不一定是最后一個），那就在函數的結尾加上一個判斷即可，如果此時的字符仍然比target小，因為字符是循環出現，所以就跳轉回第一個字符

AC代碼

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;
const int N = 101;char target;
string str;
bool check(int x)
{return str[x]-97> target-97;
}
char StrBinarySearch()
{int l, r;l = 0, r = str.length()-1;while (l < r){int mid = l + r>>1;if (check(mid))r = mid;else l = mid + 1;}if ((l == str.length() - 1 || str[l] == str[str.length() - 1]) && str[l] < target)l = 0;return str[l];
}
int main()
{int t;cin >> t;while (t--){cin >> str >> target;cout << StrBinarySearch() << endl;}return 0;
}