我有一个字符串数组排序：例如：酒吧，富，顶，斑马]我想搜索，如果输入一个词是present在一个阵列。

例如：

 搜索（字符串[]海峡，串词）{
     //二进制搜索实现+字符串助动词。
}
 

现在二进制搜索将占复杂度是O（LOGN），其中n是一个数组的长度。所以这么好。

不过，在某些时候，我们需要做一个字符串比较，它可以在线性时间内完成。

现在的输入数组可以包含不同大小的字。所以，当我   我最后的计算复杂度将最后的答案是O（M * LOGN）   其中， M 是字，我们希望在阵列中进行搜索，其规模在我们的情况下，   是斑马我们要搜索​​的字？

是的，你的想法以及你提出的解决方案，两者都是正确的。您需要考虑的最长的字符串的长度过的字符串搜索的整体复杂性。

一个平凡的字符串比较是 O（M）操作，其中 M 是较大的长度这两个字符串。

不过，我们可以提高很多，因为数组排序。当用户doynax表明，

复杂性可以通过保留多少个字中得到匹配的轨道得到改善   的字符串比较，并存储present计数的下限和   在搜索过程中上限。由于数组进行排序，我们知道   中间条目接下来要测试的preFIX最多必须匹配到在   至少最小的两个深度的，因此，我们可以跳过   比较了preFIX。实际上我们总是要么取得进展   或不匹配立即停止增量进行比较，而且   从而永远需要继续下去了旧地面。

因此​​，总体而言 M 的字符比较数将不得不做，直到字符串的结尾，如果发现或者甚至没有那么多的（如果未能在早期阶段）。

所以，整体的复杂性将是 O（M + log n）的。

I have an sorted array of strings: eg: ["bar", "foo", "top", "zebra"] and I want to search if an input word is present in an array or not.

eg:

search (String[] str, String word) {
     // binary search implemented + string comaparison.
}

Now binary search will account for complexity which is O(logn), where n is the length of an array. So for so good.

But, at some point we need to do a string compare, which can be done in linear time.

Now the input array can contain of words of different sizes. So when I am calculating final complexity will the final answer be O(m*logn) where m is the size of word we want to search in the array, which in our case is "zebra" the word we want to search?

Yes, your thinking as well your proposed solution, both are correct. You need to consider the length of the longest String too in the overall complexity of String searching.

A trivial String compare is an O(m) operation, where m is the length of the larger of the two strings.

But, we can improve a lot, given that the array is sorted. As user "doynax" suggests,

Complexity can be improved by keeping track of how many characters got matched during the string comparisons, and store the present count for the lower and upper bounds during the search. Since the array is sorted we know that the prefix of the middle entry to be tested next must match up to at least the minimum of the two depths, and therefore we can skip comparing that prefix. In effect we're always either making progress or stopping the incremental comparisons immediately on a mismatch, and thereby never needing to keep going over old ground.

So, overall m number of character comparisons would have to be done till the end of the string, if found OR else not even that much(if fails at early stage).

So, the overall complexity would be O(m + log n).