News for hackers. Stuff that matters.
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.