Binary Search

[kmj]

Okay, I know that a binary search is big-O of lg n; it's also theta of log n, right? (meaning it's big-0 of lg n and big Omega of log n.. yeah I think so..)


:)

[Grizzly]

I found this here (http://www.chiark.greenend.org.uk/~sgtatham/algorithms/blocksort.html)


The searching procedure is similar. A binary search takes O(log n) comparisons, so in the worst case the search can take O(N log H). Assuming the needle is reasonably small, this seems entirely acceptable for the massive gain of not having an O(H) term!