Find index in string array where strings change from "good" to "bad" - interview question

Question

You are given a string array named strs with length n, when each string can have the value "good" or "bad". It is also known that exists index i so that:
0<=i<=n-1, strs[0]=strs[1]=...=strs[i-1]="good", strs[i]=strs[i+1]=...=strs[n-1]="bad".
Pay attention that if i=0, it means that strs has only strings with the value "bad".

Write an algorithm to find index i.
Desired run time: O(logn)

My attempt:
I'm sure you need to use binary search here, but for some reason I have a problem with the check of the middle element.
I thought of checking if the middle element has a value of "good" and the middle+1 element has a value of "bad", but this can give out of bounce error.

Any idea how to solve it?

Answer 1

In this answer over here, I explain that when you write a binary search, it's usually better to do a real binary search (making real binary decisions) to find the index where the element you're searching for belongs, and then check to see if it's actually there:

How can I simplify this working Binary Search code in C?

In your case, the index is your desired result, so you don't even need to check:

int findIndex(string[] array)
{
    int minpos=0;  //smallest possible answer (array is all bad)
    int limit=array.length; //largest possible answer (array is all good)

    while(minpos<limit)
    {
        //testpos is guaranteed to be >= minpos and < limit
        int testpos = minpos+((limit-minpos)/2);

        if (array[testpos].equals("good")) //test index is too low
            minpos=testpos+1; //minpos always increases here  
        else
            limit=testpos; //limit always decreases here
    }

    return minpos;
}