Binary Search Reconsidered (2018) (solipsys.co.uk)

  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;
  }

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)

https://algorithmica.org/en/eytzinger

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

  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 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.

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

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.

    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)
    }