https://bugzilla.wikimedia.org/show_bug.cgi?id=164
--- Comment #222 from Philippe Verdy <verd...@wanadoo.fr> 2011-07-20 13:18:31 UTC --- You should know that a binary search for equality of for lower bound is completely the same algorithm. (If not convined, look at the source of a C++ standard library, which uses the same function for both: finding exact matches or finding a lower bound for inserting a new item). The difference only occurs at end of the loop, about what you return when an exact equality is not found. In both cases, the binary search loop will terminate with min=max+1 exactly if no exact match is found, so that max is the lower bound you want. My suggestion fixes a few things: - it uses a while()... instead of a do...while() which is incorrect for the case where the search space opperates with count<2. - it has faster convergence - it contains no special case to handle (your code will be erroneous in those cases). - even when searching with count=0, it starts with min=0 and max=-1, which terminates the loop immediately, with the same condition for not found (max < min, and max if the lower bound) - it works with count=1 without creating an infinite loop like in your code when the target is higher that the only element [0] to check, because it ensures that the loop will ALWAYS reduce the search space at each interation. -- Configure bugmail: https://bugzilla.wikimedia.org/userprefs.cgi?tab=email ------- You are receiving this mail because: ------- You are on the CC list for the bug. _______________________________________________ Wikibugs-l mailing list Wikibugs-l@lists.wikimedia.org https://lists.wikimedia.org/mailman/listinfo/wikibugs-l
