News for hackers. Stuff that matters.
Re:Binary Search Reconsidered (2018) by justinpombrio on Friday December 25, 2020 @01:22PM (#25538062)
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.
Re:Binary Search Reconsidered (2018) by tsimionescu on Friday December 25, 2020 @03:46PM (#25538912)

  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.
Re:Binary Search Reconsidered (2018) by justinpombrio on Friday December 25, 2020 @10:49PM (#25541231)
> 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.

Re:Binary Search Reconsidered (2018) by klyrs on Friday December 25, 2020 @03:04PM (#25538645)

  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?

Re:Binary Search Reconsidered (2018) by __s on Friday December 25, 2020 @03:21PM (#25538757)
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)
Re:Binary Search Reconsidered (2018) by tsimionescu on Friday December 25, 2020 @03:49PM (#25538928)
> Do slices give access to their underlying offset?

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

Re:Binary Search Reconsidered (2018) by klyrs on Friday December 25, 2020 @04:40PM (#25539252)
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.
Re:Binary Search Reconsidered (2018) by tsimionescu on Saturday December 26, 2020 @01:16AM (#25541809)
Oops, you're absolutely right. I completely forgot that the array variable was being modified itself.
Re:Binary Search Reconsidered (2018) by TedShiller on Friday December 25, 2020 @02:47PM (#25538552)
That’s considered clean?
Re:Binary Search Reconsidered (2018) by tsimionescu on Friday December 25, 2020 @03:48PM (#25538920)
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.
Re:Binary Search Reconsidered (2018) by klyrs on Friday December 25, 2020 @04:57PM (#25539355)
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.