第一个使用O(log n)的大写函数

Question

我编写了以下代码来查找字符串中的第一个大写字母:

char first(const char str[], int n)
{
for (int i = 0; i < n; i++)
if (isupper(str[i]))
return str[i];
return 0;
}

代码工作，但我需要通过使用O(log n)操作来修改它，我相信这是二进制搜索。我如何修改代码来遵循它?任何提示/建议都会有所帮助。(const char str[]为字符串，int n为字符串的长度)

编辑:所有小写字母出现在大写字母之前

Answer 1

As "小写字母出现在大写字母之前，我们可以使用二分搜索来查找大写字母。现在如果我们找到一个大写字母我们就检查相邻的左字符。如果它是大写的，那么显然第一个大写字符位于当前找到的大写字符的左边。如果不是，那么我们找到第一个大写字符。否则，我们将继续在字符串的右侧搜索。

二进制搜索的实现将是:

char first(const char str[], int n){
int low = 0;
int high = n-1;
while(low<=high){
mid=(low+high)/2;
if(isupper(str[mid]){
if(mid >0){ //we can't access negative index
if(!isupper(str[mid-1]){ //if adjacent left char is not capital, then this is first Capital char
return str[mid];
}else {
high=mid-1; //as this is not first Capital char, search left
}
else{
return str[mid]; //as mid is first char of string and capital as well
}
}
else {
low=mid+1;
}
}
return 0;
}