我有一个排序的字符串数组：例如：[“bar”，“foo”，“top”，“zebra”]我想搜索输入字是否存在于数组中 .
例如：
search (String[] str, String word) {
// binary search implemented + string comaparison.
}
现在二进制搜索将考虑复杂度，即O（logn），其中n是数组的长度 . 所以这么好 .
但是，在某些时候我们需要进行字符串比较，这可以在线性时间内完成 .
现在输入数组可以包含不同大小的单词 . 因此，当我计算最终复杂度时，最终答案是O（m * logn），其中m是我们想要在数组中搜索的单词的大小，在我们的例子中，“zebra”是我们要搜索的单词？
1 回答
是的，您的想法以及您提出的解决方案都是正确的 . 在String搜索的整体复杂性中，您还需要考虑最长String的长度 .
一个简单的字符串比较是
O(m)操作，其中m是两个字符串中较大者的长度 .但是，鉴于数组已排序，我们可以进行很多改进 . 正如用户"doynax"所暗示的那样，
因此，如果发现字符串的结尾，则必须进行整体
m次字符比较，否则甚至不会那么多（如果在早期阶段失败） .因此，整体复杂性将是
O(m + log n).