在字符串数组中查找索引，其中字符串从“好”变为“坏”

-1

当给每个字符串赋值 "good" 或 "bad" 时，会给出一个名为 strs 且长度为 n 的字符串数组 . 还知道存在索引 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" ，但是这可以避免跳出错误 .

知道怎么解决吗？

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

回复于 2024-05-06T22:08:30+08:00

在字符串数组中查找索引，其中字符串从“好”变为“坏” - 面试问题

1 回答

相关问题