using binary search to find the first capital letter in a sorted string [closed]

Question

I wrote the following code to find the first capital letter in a string using binary search:

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;
}

Currently my code isn't working as expected while testing it. If anyone can mention where I went wrong it would help a lot.

NOTE: The input string will be already sorted (all lower case letters appear before upper case letters). const char str[] is the string and int n is the length of the string.

EDIT: for example: first_capital("abcBC", 5) should return 'B'.

Answer 1

Your logic is completely right, but you returned the wrong value

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;
}

The driver code

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

will be giving 15 as an answer which is the index of the character Z.

if u want the character to be returned replace return mid with return str[mid] and 'Z' will be returned.