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?

Using a trie (tree such that every path from the root contains a word), the complexity of a search can be lowered to just O(m) in the worst case, whatever n. — user1196549
– user1196549, Commented Oct 31, 2015 at 16:43
@YvesDaoust - I agree with you regarding the best optimal implementation, but, it seems OP was more interested in knowing the complexity of such an operation. BTW, nice of you to list that here. — Am_I_Helpful
– Am_I_Helpful, Commented Oct 31, 2015 at 18:12
@Am_I_Helpful: following your logics, why don't you move your description of the improved approach to a comment ? — user1196549
– user1196549, Commented Oct 31, 2015 at 19:22
@YvesDaoust - As per you, no one should ask for solutions of trivial problems, instead everybody(including beginners) should start solving the most optimal solution instead of knowing about the basics! Now what do you have to say on your logic? My comment was not any kind of attack to you. — Am_I_Helpful
– Am_I_Helpful, Commented Oct 31, 2015 at 20:12

Community · Accepted Answer · 2017-05-23 12:30:48Z

4

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).

edited May 23, 2017 at 12:30

CommunityBot

11 silver badge

answered Oct 31, 2015 at 15:58

Am_I_Helpful

19.2k7 gold badges53 silver badges76 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

doynax Over a year ago

In a naive implementation, yes, but if the length of the strings are significant you can skip previously matched prefixes in the comparison. Effectively you'll only need to match each string character twice, on the lower and upper bounds, rendering the search an O(log n + m) operation.

Am_I_Helpful Over a year ago

@doynax - No, I think at every depth, the string will be compared to check if they match. So, O(log n) has to be multiplied with O(m) for the comparison at every level. So, I think that the worst case analysis would be the same, i.e., O(log n * m). DO you still disagree?

JavaDeveloper Over a year ago

@Am_I_Helpful I just edited the question, m is not the size of longest word in an array, but m is the size of word we want to search. Let me know if it sounds correct ?

doynax Over a year ago

@Am_I_Helpful: The trick is to keep 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.

Am_I_Helpful Over a year ago

@doynax - Oh, I see. How couldn't I think this myself! Thanks, I am including your point in my answer wrt to your name.

|

synergy77 · Accepted Answer · 2022-01-30 15:22:54Z

0

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.

edited Jan 30, 2022 at 15:22

answered Jan 30, 2022 at 15:08

synergy77

297 bronze badges

Collectives™ on Stack Overflow

Complexity of binary search on a string

2 Answers 2

6 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related