Wednesday, August 10, 2011

Whats the complexity of a binary search algorithm for finding multiple values?

Hi there, I am trying to determine the complexity of a binary search algorithm for finding multiple values. ume, I have a sorted array of 100 elemens that contains two numbers I am looking for. I could, of course, perform a search twice which would bring me to 2*(log2(100)+1). However, since certain steps in the search overlap, the complexity should be lower.

No comments:

Post a Comment