Complexity of binary search on a string

Question

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?

Answer 1

I was under the impression that what original poster said was correct by saying time complexity is O(m*logn).

If you use the suggested enhancement to improve the time complexity (to get O(m + logn)) by tracking previously matched letters I believe the below inputs would break it.

arr = [“abc”, “def”, “ghi”, “nlj”, “pfypfy”, “xyz”]

target = “nljpfy”

I expect this would incorrectly match on “pfypfy”. Perhaps one of the original posters can weigh in on this. Definitely curious to better understand what was proposed. It sounds like matched number of letters are skipped in next comparison.