This is a follow-up to the original article where I looked at a few ways to improve my Rust implementation of Binary search - with a focus on removing 'mistakes' and making it as 'idiomatic' as possible.
The most common piece of feedback I received on the first article
was related to the comparison between the middle
value and high
/low
cursors.
In my original Tweet (even before the first article) I had presented a variant of the algorithm
that used pattern matching for this comparison via Rust's match
construct.
One of my first attempts
rust
pub fn binary_search_alt(k: i32, items: &[i32]) -> Option<i32> { let mut low: i32 = 0; let mut high: i32 = items.len() as i32 - 1; while low <= high { let middle = (((high + low) / 2) as f64).floor() as i32; match items.get(middle as usize) { Some(current) if *current == k => return Some(middle), Some(current) if *current > k => high = middle - 1, Some(current) if *current < k => low = middle + 1, _ => {} } } None}
If we apply the feedback from the first article to this implementation, we'd end up with the following - which is just a bit cleaner since it removes some casting along with the manual 'flooring' I was originally doing.
rust
pub fn binary_search_alt(k: i32, items: &[i32]) -> Option<usize> { let mut low: usize = 0; let mut high: usize = items.len() - 1; while low <= high { let middle = (high + low) / 2; match items.get(middle) { Some(current) if *current == k => return Some(middle), Some(current) if *current > k => { if middle == 0 { return None; }; high = middle - 1 } Some(current) if *current < k => { low = middle + 1; } _ => {} } } None}
This is where it became a bit complicated. I originally received some feedback on Twitter
that suggested because I'm not using the return value of the match
block in any of the arms, along with
the fact that I'm only using it to mutate the high/low cursors, that this could be deemed not idiomatic Rust...
I fully understood that feedback, and to rectify the match could be written like so:
rust
match items.get(middle as usize) { Some(current) if *current == k => { return Some(middle); }, Some(current) if *current > k => { if middle == 0 { return None }; high = middle - 1; }, Some(current) if *current < k => { low = middle + 1; }, _ => {}}
Now each match arm has no trailing expression, possibly making it clearer to the next developer that we didn't intend on returning a value here from the match block.
Is this implementation more idiomatic? I'm not entirely sure.
There are 2 reasons that I'm not sure about this.
1: Rust makes heavy use of pattern matching, and whilst match
is technically an expression
itself (and therefore can be used as a value), I don't think it's an issue if it's not always used as a value?.
2: It seems like it would be more of an issue if each arm of the match had different semantics. For example, if one
arm returned a value and another didn't. This would make the implementation inconsistent,
and the viewpoint may hold more water, but Rust's type system will not allow this anyway since each
arm of the match
must return the same value.
For those 2 reasons, the rest of this post will focus on further improving our algorithm
to fully utilize match
- but please reach out on Twitter if you disagree, I'd love
to continue the conversation 😀
Option
Our algorithm is searching within a slice of i32
values. On each iteration we are accessing a value from the slice
with the .get()
method. This was done for safety since a runtime panic can occur if you attempt
an index-access with a value that would be out-of-bounds.
rust
fn this_will_panic() { let items = vec![10, 40, 90]; let forth_item = items[3]; println!("{:?}", forth_item) // 'main' panicked at 'index out of bounds: // the len is 3 but the index is 3'}
rust
fn this_will_not_panic() { let items = vec![10, 40, 90]; let first_item = items.get(0); println!("{:?}", first_item); // prints `Some(10)` let forth_item = items.get(3); println!("{:?}", forth_item) // prints `None`}
So the second way of accessing a value may be safer, but it comes at the cost of an additional layer
of indirection in the form of that Option
type.
rust
// return type is Option<i32>let item = items.get(4) // return type is i32, but may paniclet item = items[4]
This affected our algorithm in the first article since we needed to use an if let
expression to expose the current value via the Some(current)
pattern.
rust
// ↓↓↓↓↓↓↓↓↓↓↓↓if let Some(current) = items.get(middle) { if *current == k { // snip } if *current > k { // snip } if *current < k { // snip }}
So, to remove the Option
and therefore also remove .get()
and Some(current)
, we'd need to be mathematically
sure to be within the slice bounds - otherwise we'd get a runtime panic! Well it turns out that our original
algorithm was actually doing all the checks we need - it always ensures the next index access is above zero and is below
the max length of the slice.
This means that in terms of the original article, we could've replaced the if let Some(current)
with a simple index
access which makes the solution less syntactically noisy and is simpler overall.
rust
// we know this won't panic since we control 'middle'// ↓↓↓↓↓↓↓↓↓↓↓↓↓let current = items[middle]if current == k { // snip}
Now we can be confident that a direct index access is always safe, since we control the middle
value, but how does
this help us with the match expression mentioned previously?
If all we did was take the match
expression from the beginning of this article, and remove the Option
as mentioned
above, we'd end up with something that looked like this
rust
// beforematch items.get(middle) { Some(current) if *current == k => return Some(middle), Some(current) if *current > k => { if middle == 0 { return None }; high = middle - 1 }, Some(current) if *current < k => { low = middle + 1; }, _ => {}} // aftermatch items[middle] { current if current == k => { return Some(middle); }, current if *current > k => { if middle == 0 { return None }; high = middle - 1 }, current if *current < k => { low = middle + 1; }, _ => {}}
Which is barely even an improvement 🙁! If anything, I'd say it's actually harder to read.
It's missing the next big step, which is also another move towards more idiomatic Rust - and that's to take advantage
of the fact that the Ord
trait is implemented for i32
in the standard library.
The Ord
trait has a .cmp(other)
method which returns a variant of the Ordering
enum, it's definition
looks like this...
rust
// std::cmppub trait Ord: Eq + PartialOrd<Self> { fn cmp(&self, other: &Self) -> Ordering; // snip}
... and an example in isolation would look like this:
rust
fn main() { let first: i32 = 1; let second: i32 = 3; let result = first.cmp(&second); println!("result = {}", result) // outputs `Less`, `Greater` or `Equal` respectively}
Notice how this is consolidating 3 separate comparisons into a single method call -
it removes the need to manually check equal
, greater
, and less
in an imperative style and instead it ends
up being more declarative since we're no longer defining the actual implementation.
After the call to .cmp(other)
we now have a value which is equal to one of Ordering
's 3 enum variants
and this is where languages with Pattern Matching really shine since we can do a match
on the variant and
simplify our code quite a bit.
rust
match items[middle].cmp(&k) { Ordering::Equal => return Some(middle), Ordering::Greater => { if middle == 0 { return None }; high = middle - 1 }, Ordering::Less => low = middle + 1}
Along with being a more declarative style, it's also much less noisy with far fewer things to mentally parse. 😇
Also, since the matching on the Ordering
enum is exhaustive, we no-longer need
the empty _ => {}
as a final catch-all match arm either. 🙏
A final thing to note here is that since we're invoking a method implemented for the Ord
trait, it means that
our algorithm could be made more generic in the future to include searching for any type that implements Ord
, and
not just i32
as in our example. This would make a great follow-on blog post, highlighting the power of traits in Rust, please
reach out to me on Twitter if you'd like to see that post happen 🐦
After applying both improvements documented so far (removing Option
+ doing a single comparison) we end up with
the following implementation - which is clearly a big improvement 👌.
rust
use std::cmp::Ordering; fn binary_search(k: i32, items: &[i32]) -> Option<usize> { if items.is_empty() { return None } let mut low: usize = 0; let mut high: usize = items.len() - 1; while low <= high { let middle = (high + low) / 2; match items[middle].cmp(&k) { Ordering::Equal => return Some(middle), Ordering::Greater => { if middle == 0 { return None }; high = middle - 1 }, Ordering::Less => low = middle + 1 } } None}
usize
dropping below zero.There are 2 lines in our implementation that still feel 'over-engineered' - or rather, it feels like they could be improved, or removed.
rust
// this is the opening check in the functionif items.is_empty() { return None } // part of the `Greater` match arm, need to// ensure we don't subtract below zeroif middle == 0 { return None };
To solve this, we need to address the core algorithm. If we define high
as the exclusive upper bound
and only ever re-assign it to either the length of the slice at the start of the function, or to a subsequent
middle value, we can be sure that we'll never decrease its value below zero, and therefore we can remove
both of the checks mentioned above.
We'd be ensuring that none of the mutable usize
cursors can ever drop below zero, and that would allow us to remove those
two manual checks.
That leaves us with the following, which I'm starting to feel happy about after these 2 long blog posts & the feedback I received on Twitter 🙏
rust
use std::cmp::Ordering; fn binary_search(k: i32, items: &[i32]) -> Option<usize> { let mut low: usize = 0; let mut high: usize = items.len(); while low < high { let middle = (high + low) / 2; match items[middle].cmp(&k) { Ordering::Equal => return Some(middle), Ordering::Greater => high = middle, Ordering::Less => low = middle + 1 } } None}
This first visualization here shows how all the demos across both posts (apart from the final change) play out
Original
This next visualization shows how much simpler everything becomes when you have high
as the exclusive upper bound - fewer steps are taken overall. Also note how the high
cursor begins at 1 index higher than the end of the list, whereas previously it began
on the last element directly.
Exclusive upper bound
A huge thanks to Wiebe Cnossen and Basile Henry for providing the feedback that inspired this follow-up post.
I'd love to hear any feedback or alternative ways to implement this algorithm in Rust - so please reach out on Twitter if you have any thoughts 🦀