Binary Search Reconsidered (2018) | Hacker News Reader

Binary Search Reconsidered (2018)

solipsys.co.uk

69 pointstomcam48 comments

Slices in Rust make for a clean solution:

  fn binary_search<T: Ord>(mut array: &[T], key: T) -> Option<T> {
      use std::cmp::Ordering::*;
  
      while !array.is_empty() {
          let middle = array.len() / 2;
          match key.cmp(&array[middle]) {
              Less => array = &array[..middle],
              Equal => return Some(key),
              Greater => array = &array[middle + 1..],
          }
      }
      None
  }

The type &[T] is a slice. Under the hood it consists of a pointer into an array, plus a length. So it (i) does some bookkeeping for you and reduces the number of variables you need by 1, and (ii) avoids the "lower + upper overflow" issue.

  fn binary_search<T: Ord>(mut array: &[T], key: T) -> Option<T>

A more useful signature would have been

  fn binary_search<T: Ord>(mut array: &[T], key: T) -> Option<usize>

And then returning `Some(middle)` on the Equal match. Returning the value you were given or None would be better expressed as returning True/False to avoid the unnecessary copy.

> A more useful signature would have been [returning the index].

Good point! And if you're doing that, there's no reason to use slices. So I guess the only thing to learn from my code... is that slices do useful bookkeeping for problems similar to this, in the case that you don't care about the indices?

> Returning the value you were given or None would be better expressed as returning True/False to avoid the unnecessary copy.

Just because two values are equal, doesn't mean they're the same. Though my function signature was wonky, regardless.

  Equal => return Some(key),

The article's implementations return the index, not the value being searched for as you've done here. Do slices give access to their underlying offset?

Also the article manages a single branch per iteration. How well does this cmp / match perform in comparison?

For reference, this is rust's actual binary search implementation: https://doc.rust-lang.org/src/core/slice/mod.rs.html#1841 (returns either Ok(index) when element exists, or Err(index) where index is where you'd insert the element when it doesn't exist)

> Do slices give access to their underlying offset?

They don't have to, you already have `middle` available, they can just return Some(middle)

No, middle is an index into a slice with an arbitrary offset. Unless (with probability ≈ 0.5^log(n)) you've picked the lower half every time before finding the element, that is not the correct index.

Oops, you're absolutely right. I completely forgot that the array variable was being modified itself.

That’s considered clean?

What do you consider not to be clean? I dislike the fact that it returns a copy of the key, but otherwise it seems quite explicit code that doesn't needlessly get bogged down in error prone integer arithmetic.

As I've pointed out in another comment, this implementation loses track of the index. It looks clean enough to my un-rusty eye, but it sacrifices functionality in favor of hiding the arithmetic behind a slice.

And __s's comment does it best: use the standard library. And that's a nice implementation (despite the unsafe stuff), which tracks the basepoint and size to keep the arithmetic clean.

The Competitive Programmer's Handbook by Antti Laaksonen (pllk) [0] presents an alternative formulation which seems fairly intuitive to derive. The idea is to take a "normal" for-loop iterating through the entire array (a constant step size of 1), and instead use a large initial step size (n/2) which halves at each iteration.

[0] https://cses.fi/book/index.php

I wonder if it's easier to write an eytzinger binary search (which is also cache-aware and therefore faster):

https://algorithmica.org/en/eytzinger

Funnily enough, the first example of a standard binary search contains the same overflow error.

The problem with eytzinger representation is that it is infinitely less useful, and really can only be used as write-once read-many lookup or cache but not as primary storage that is also a cache because it is no longer contiguous.

eg Etyzinger is awesome, but in most real world usage something like this is far more practical and ultimately performant: Faster Lookups, Insertions, and In-Order Traversal Than a Red-Black or AVL Tree [0].

[0]: https://neosmart.net/blog/2019/sorted-list-vs-binary-search-...

You're right about that, but I recently ran into a situation where I had to process about a TB of data repeatedly in that configuration. As a serialized file format, Eytzinger rocked. The IO cost probably dominated, but there was no reason not to use it.

Conveniently, we are not shown the type of n or its valid input range: if it is a int16_t or we know it to be upper bounded by 1<<30, that's proper vanilla binary search.

Usually when I'm doing a binary search, I'm not searching over integers, so the comparison itself will be quite expensive compared to the rest of the loop, so I prefer it like this:

  int BinarySearch<t>(t[] array, t find, int min, int max, Comparer<t> comparer)
  {
      int mid = 0;
      while (min <= max)
      {
          mid = (int)(((long)min + (long)max) / 2);
          int compared = comparer.Compare(find, array[mid]);
          if (compared > 0)
              min = mid + 1;
          else if (compared < 0)
              max = mid - 1;
          else
              return mid;
      }
      return ~mid;
  }

The bug as pointed by the article would be here:

"Specifically, it fails if the sum of low and high is greater than the maximum positive int value (231 - 1). The sum overflows to a negative value, and the value stays negative when divided by two." -https://ai.googleblog.com/2006/06/extra-extra-read-all-about...

This particular overflow is pretty famous as a bug, but it's always annoyed me. If you have a 32 bit address space and use a 32 bit integer, the only way this would reasonably overflow is if you have a single array of sorted bytes consuming half or more of the address space. Surely there must be a better data structure to use when you're keeping track of sorted bytes filling that much memory. For instance an array of 256 integers can contain the exact same information consuming only a tiny fraction of the space.

As soon as your array is storing objects that are 2 bytes or larger, you can't overflow the unsigned integer any more. The same applies for a 64 bit address and 64 bit integers. Never mind that most 64 bit hardware in existence is actually limited to a 48 bit address space, in which case the bug CAN NOT be exercised even with signed integers.

These issues would be a lot less troublesome if hardware offered basic security, like zero-cost poison-on-overflow and bounds-checked pointers, either of which would solve any risks of just letting it be. But right now there's the pragmatic question of not only whether this is a bug you could hit accidentally, but whether it's a bug you could exploit intentionally to corrupt memory, so it's better to just do the technically-correct thing even if it seems pointless.

It's less concerning for C#, which is a managed language, of course.

In Java (I think that is the implementation language,) longs are 64bit and ints are 32bit, so I think this problem doesn’t come up

It did at one point, I recall Sun had that exact bug at some point back around 1.4, I remember it being fixed. Of course the long conversions alleviate the problem but at a performance cost and its an avoidable cast.

No java doesn't use 64bits at all. It uses unsigned right shift. I mentioned it in another post: "int mid = (low + high) >>> 1;"... And for the older timers (14y ago), there used to be a bug[0] about exactly that.

[0] https://bugs.openjdk.java.net/browse/JDK-5045582

This is my go-to implementation, but I make one little tweak. It’s very unlikely that you will overflow a long, but you can you guarantee that you’ll avoid overflow like this:

mid = min + (max - min) / 2;

In x86 (intel notation) you can also:

add rax, rbx

rcr rax, 1

It explicitly uses the carry flag from the addition as the top bit of the right-rotated result.

Not super useful for anything other than averaging two uints but that's x86 for you.

What I missed in my first pass was

   * Forgetting exactly which register was the low index and which was the high index
   * Underflow if array size was zero from setting the last index to (size - 1)

If the unsigned right shift is defined (java): "int mid = (min + max) >>> 1;"

edit: this is a bit longer version, if signed conversion/shift is not available: int mid = (min >> 1) + (max >> 1) + (min & max & 1)

That's my C# implementation, so long is 64 bits and int is 32 bits. 64 bits will never overflow in my lifetime. That's basically a Google scale amount of data.

can you explain to me how that fixes it? Thanks

There is an implicit invariant that 0 <= min, and min <= max, so max - min is between 0 and int_max inclusive, so you avoid overflowing with that calculation. To be sure that you avoid overflowing at the sum step, you need to prove that min + (max - min) / 2 <= max.

what if max is already overflown due to size of array (without even doing the lo + high calculation?) Then min + (max- min)/2 would be min + (smaller negative value) which would violate the min + (max-min)/2 <= max

Assuming the value of max passed in is "sane" (non-negative and within array bounds), it is strictly decreasing and should never overflow.

This makes sure that none of the quantities being calculated will overflow while still returning the same answer.

Where x is min and y is max, the midpoint is:

(x+y)/2 = x+(y-x)/2 x+y = 2x+y-x x+y=x+y

This is what I ended up with:

    fn search<T: Ord>(haystack: &[T], needle: &T) -> Result<usize, usize> {
        let mut range = 0..haystack.len();
        while !range.is_empty() {
            if range.len() == 1 {
                if &haystack[range.start] == needle {
                    return Ok(range.start);
                } else {
                    return Err(range.start + 1);
                }
            }
        
            let search_range = &haystack[range.clone()];
            let (left, right) = search_range.split_at(search_range.len() / 2);
            
            if needle < &right[0] {
                range.end -= right.len();
            } else {
                range.start += left.len();
            }
        }
        
        Err(range.start)
    }

I'm not overly happy with the break conditions inside the loop. They feel messy.

I remember reading the part about binary search in Programming Pearls and it left a big impression on me. It is a very neat example because it's something that everyone thinks they know how to do, but there are enough places to introduce an off-by-one error that it is very easy to mess up if you aren't careful.

The big takeaway for me was the importance of thinking about invariants, and of documenting said invariants in comments next to the code. It has become my go-to example if I need to teach someone about invariants.

Lots of implementations here: https://rosettacode.org/wiki/Binary_search. The J implementations are beautiful.

As soon as I read this I got paranoid and whipped one out, I am not sure if I missed edge cases

def binary_search(numbers: List[int], target: int) -> int:

    if not numbers:
        return -1
    if len(numbers) == 1 and numbers[0] != target:
        return -1

    middle = math.floor(len(numbers) / 2)

    if numbers[middle] == target:
        return target
    elif numbers[middle] > target:
        return binary_search(numbers[0: middle], target)
    else:
        return binary_search(numbers[middle + 1:], target)

Note that you're copying one half of the list into a new list at each recursive call, making the algorithm O(n). Better to pass the original list and use indices to indicate which portion you're working on

Suppose he changed the type of numbers from List[int] to Tuple[int]. Would that get rid of the copying?

Tuples are immutable in Python, so in theory it should be able to but I have no idea if Python actually makes that optimization.

Even if it does, this is probably not a good approach in Python because Python does not optimize away tail recursion.

Python will reclaim/reuse tuples sometimes, but I'm unsure if it will fully "intern" them the way it does for ints (and java does for some strings).

Regardless, even if that optimization is present, the overhead of checking and deduping the tuples against the intern cache as they are constructed after the split operations would likely be considerable. Indexes would likely remain the very fastest strategy.

An optimization theoretically exists which could make tuple splitting as fast as index accounting (representing split results as slices/views into the original tuple), but I do not believe python does that, as it would cause unexpected memory growth in some situations, unless accompanied by a very specialized garbage collection scheme.

great suggestion

The first error I spotted was on line 9.

Yeah, why worry about edge cases if you can't get the basic algorithm right?

Python is exceptionally bad at recursion. Binary search isn't the most egregious use case, as the call depth is logarithmic... but the call overhead is hefty and recursive algorithms are generally bad practice because of the low ceiling.

If you code this right, there's no need for the two special checks at the start of the function - they just naturally get resolved.

These days I mostly use Java and Python. They both ship with a binary search implementation.

What nobody says about binary search is that it is very, very slow on modern hardware.

The reasons it is slow are interesting and useful to understand.

On modern equipment, to get decent performance, everything needs to pipeline, so you start an operation and get the answer out 3, 5, sometimes 12 cycles later. In the meantime, you're pushing new operations into the pipeline so that useful answers will come out the cycle after. To keep pipelines (plural; there are lots) full, we have "branch prediction": the CPU doesn't know which way an upcoming conditional branch will go, so it guesses. It has a neural network to remember how this branch went other times, that is quite clever. When it guesses right, all is good, and the pipeline stays full. When it guesses wrong, it has gone off doing lots of wrong computations that have to be thrown away, and the pipeline restarted at the correct spot.

Binary search presents the worst case for prediction. At each stage, any prediction is 50% likely to be wrong. You hardly get two steps into your pipeline before it turns out you were wrong, and have been doing the wrong thing.

There are ways to reduce the worst effects, but they make the algorithm much less pleasant to read, and even trickier to get right. One is to use clever arithmetic to arrange that the same instruction sequence runs whichever way the choice goes. Another is to split the range into more than two subranges, so the choice is made less often--log base 3 or -base 4 iterations, instead of two. Maybe you pre-fetch values you expect to look at soon: half of them will be ones you won't actually need, and you won't know which until later, but you didn't need to wait for the right one.

Once a range gets small enough, you do better searching sequentially, because CPUs are tuned to do that very fast.

Hash tables avoid all this foolishness, and (so) can be very fast.

To write good, fast code for things like binary search, intuition is entirely inadequate. You really need to pay a lot of attention to "performance counter" registers modern chips have, that can tell you about prediction failures and cache misses that slow you to a crawl. It is humbling to discover how wrong all we learned in school, about algorithm performance, is.

When you home in on a code sequence that minimizes pipeline bubbles, you have to expect that the next generation of CPU chips will have completely different details, and that what was fast is now slow.

The deep lesson is that we never know if our code is fast until we find code that is faster; what seemed fast becomes slow in an instant. All the other old faithful algorithms, like Quicksort, can be easily 2x faster or slower according to obscure details that are hard to reason about.

It makes some people decide that 2x, 4x, 100x, or 1000 times slower than necessary ought to be considered fast enough.

I really enjoyed reading your comment. Do you maintain a blog where you discuss such matters?

You’re not wrong, just off topic.

Reply on news.ycombinator.com