在字符串数组中查找字符串从 "good" 变为 "bad" 的索引 - 面试问题

Question

给定一个名为 strs、长度为 n 的字符串数组，其中每个字符串的值可以为 "good" 或 "bad"。还已知存在索引 i 因此：
0<=i<=n-1, strs[0]=strs[1]=...=strs[i-1]="good", strs[i]=strs[i+1]=...=strs[n-1]="bad".
注意，如果i=0，则意味着strs只有值为"bad"的字符串。

写一个算法来查找索引i。
所需运行时间：O(logn)

我的尝试：
我确定你需要在这里使用二进制搜索，但出于某种原因我对中间元素的检查有问题。
我想检查中间元素的值是否为 "good" 并且中间+1 元素的值为 "bad"，但这可能会导致跳出错误。

知道如何解决吗？

Answer 1

在这里的这个答案中，我解释说当你写一个二分搜索时，通常最好做一个真正的二分搜索（做出真正的二分决策）来找到你要搜索的元素所属的索引，然后检查它是否真的存在：

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

在你的情况下，索引就是你想要的结果，所以你甚至不需要检查：

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

在字符串数组中查找字符串从 "good" 变为 "bad" 的索引 - 面试问题

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

arrays

algorithm

performance

binary-search