使用二分查找查找已排序字符串中的第一个大写字母

Question

我编写了以下代码来使用二进制搜索查找字符串中的第一个大写字母：

char first_capital(const char str[], int n)
{
    int begin = 0;
    int end = n - 1;
    int mid;
    while (begin <= end)
    {
        mid = (begin + end) / 2;
        if (mid == 0 && isupper(str[mid]))
        {
            return mid;
        }
        else if (mid > 0 && isupper(str[mid]) && islower(str[mid - 1]))
        {
            return mid;
        }
        if (islower(str[mid]))
        {
            begin = mid + 1;
        }
        else
        {
            end = mid - 1;
        }
    }
    return 0;
}

目前我的代码在测试时没有按预期工作。如果有人能提到我哪里出错了，那会很有帮助。

注意：输入字符串将已经排序（所有小写字母都出现在大写字母之前）。const char str[]是字符串，int n是字符串的长度。

编辑：例如：first_capital("abcBC", 5)应该返回'B'。

Answer 1

你的逻辑完全正确，但你返回了错误的值

char first_capital(const char str[], int n)
{
    int begin = 0;
    int end = n - 1;
    int mid;
    while (begin <= end)
    {
        mid = (begin + end) / 2;
        if(mid == 0 && isupper(str[mid]))
        {
            return mid;    // Here the index is returned not the character
        }
        else if (mid > 0 && isupper(str[mid]) && islower(str[mid-1]))
        {
            return mid;    // Same goes here
        }
        if(islower(str[mid]))
        {
            begin = mid+1;
        }
        else
        {
            end = mid - 1;
        }
    }
    return 0;
}

驱动程序代码

int main(){
    
    printf("%d\n", first_capital("abcabcabcabcabcZ", 16));
}

将给出 15 作为答案，这是字符 Z 的索引。

如果您希望返回字符，请替换return mid为return str[mid]并返回'Z'。