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

Question

关闭。这个问题需要debugging details .它目前不接受答案。












想改善这个问题吗？更新问题，使其成为 on-topic对于堆栈溢出。

8 个月前关闭。




Improve this 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”。