\nalways<\/em> written wrong. There’s a bit of subtlety in implementing it correctly, and virtually
\neveryone manages to put off-by-one indexing errors into their implementations. (Including me; last time I implemented a binary search, the first version included one of the classic errors.) The errors are so ubiquitous that even in a textbook that discusses the fact that most programmers get it wrong, they got it wrong<\/em> in their example code!<\/p>\n
<\/p>\n
In its simplest form, you have a list of values L={l1<\/sub>,…,ln<\/sub>}, in sorted order; and you have a value, x. You want to find out which, if any, of the li<\/sub>s is equal to x.<\/p>\n The algorithm is a simple recursive one: <\/p>\n You pick a position, i, in the middle of the list. If Li<\/sub> is equal to x, then you’ve found x at position i. If Li<\/sub> is greater than x, then you know that if x is in the list, it must be in the half of the list that’s smaller than Li<\/sub>. If Li<\/sub> is less than x, then you know that if x is in the list, then it must be in the half of the list that’s larger than Li<\/sub>. If in any of the recursions, you wind up with an empty list, then you know that x wasn’t in the list.<\/p>\n Before moving on to point out some of the interesting places this pops up, let’s take a moment to think about how complex it is. Each step of the algorithm, we either find the number we’re looking for, or we eliminate half of the list. So if in the first step, we’re searching a list of N elements, then in the second, we’ll be searching a list of N\/2 elements; in the third, we’ll be searching a list of N\/4 elements; and so on. So it takes O(lg N) steps in the worst case. <\/p>\n Is this optimal in the number of comparisons? Yes – and it’s easy to prove, using Kolmogorov-Chaitin complexity theory. If X is in the list, it could be in any one of N positions in a list of size N. How much information do we need to identify exactly one position in N? We need an integer with at least lg(N+1) bits. (Why N+1? because we also need a way to say “It wasn’t there”.) So if we’re using comparisons, which generate one bit of information per comparison, and the algorithm needs to generate lg(N+1) bits, then in the worst case, any comparison-based algorithm will need to do lg(N+1) comparisons – which is O(lg N). <\/p>\n Aside from searching sorted lists, variants of binary search pop up all over the place. For example, think about Newton’s method for finding the roots of an equation. You start with a guess; check how close it is to zero, and use the result of that to prune off part of the search space – it’s a variant binary search; constantly narrowing down the range in which the root can be found: the only real change is that you can cleverly use the derivative to narrow down the answer more quickly than a direct binary pruning. But the basic concept is the same as binary search.<\/p>\n There are a few neat examples from my research area. I do work with SCM systems – which We look at the history of the system, and we pick a point halfway through the history, and look to see if it contains that change. If it doesn’t, then we know the change was added later than it – so then we go to search the changes that happened later. It’s exactly binary search over the history of the program.<\/p>\n\nbinary_search(L=[L1<\/sub>,...,Ln<\/sub>], x)\nif L=[] then return not_found\nlet a = n\/2\nif La<\/sub> == x then\nreturn found(a)\nelse if La<\/sub> > x then\nreturn binary_search([Li<\/sub> | i < a ], x)\nelse\nreturn binary_search([Li<\/sub> | i > a], x)\n<\/pre>\n
\nnormal people sometimes call “version control systems”. A version control system is a
\nsystem that programmers use that keep a complete record of every change they’ve made to
\ntheir program – so using it, they can go back to old versions, check the history of the
\ndevelopment of their systems, etc. One thing that comes up in SCM systems is what we call
\n“blame identification”. The idea is, we know that at some time, one particular piece of
\ncode was added, and we later discovered that that piece of code introduced a bug to the
\nsystem, and we want to know exactly when<\/em> in was introduced, and who was
\nresponsible for it. How do we figure out when it got added? <\/p>\n
![\"\"](\"http:\/\/www.assoc-amazon.com\/e\/ir?t=goodmathbadma-20&l=as2&o=1&a=0201657880\")
has a great discussion of some of the other places that binary search comes up. It’s really an astonishingly common algorithm; I was totally blown away when I read Bentley’s book, and realized how many problems could be understood as variants of binary search.<\/p>\n![\"\"](\"http:\/\/www.assoc-amazon.com\/s\/noscript?tag=goodmathbadma-20\")
<\/p>\n","protected":false},"excerpt":{"rendered":"