Rust from Nothing: Implementing a Binary Search Algorithm

I spent a fair few days writing C++ in college and during internships. I enjoyed working at a lower level, working with hardware, and the feeling of being someone who worked with C++. In my eyes, only the best could use C++ and everyone else was a poser who didn’t understand memory management. The folks at Atomic quickly corrected the ill-conceived mindset I had developed around C++. I also realized that I was horrible at writing safe C++ programs. But that didn’t hold me back from loving the concept of what it meant to write low-level code. That’s when I heard of Rust from a few co-workers, and I decided I needed to check it out!

I am implementing basic algorithms and data structures to learn the language. This is my first crack!

The Algorithm

The binary search algorithm is a searching algorithm that operates on a sorted list of data. It works by comparing the middle value of the array against the value being searched for. If the value in the middle is equal to the searched value, it returns the correct value. If the value being searched for is higher than the middle of the array, it returns the higher half of the list. This is vice versa for the lower half of the list.

Here is how I used Rust to implement it!

The Simple Approach

My first crack at the problem was focused on getting a simple implementation in place. We can use a vector to handle a variable sized array of integers and use the Options type to handle a value not existing in the list. Next is creating a simple method that implements the algorithm described. See the implementation below!

fn binary_search( arr: &[usize], find: usize) -> Option {
   let length = arr.len();
   let mut half = length / 2;
   let mut hind = length - 1;
   let mut lind = 0;
   let mut current = arr[half];

   while  lind <= hind {
       if current == find {
           return Some(half);
       }
       else if current < find{ lind = half + 1; } else if current > find {
           hind = half - 1;
       }
        half = (hind + lind) / 2;
        current = arr[half];
   }
   return None;
}

The Rust-y Approach

Does the above solution work? Yeah. Is it a good implementation or an idiomatic version of the algorithm using Rust? No. It has Rust syntax, but doesn’t take advantage of any of Rust’s built-in operators. Lets look at the “yuckiest” part of the algorithm: the logic statements. Using the match operator, we can set different indices much more efficiently.

fn find_index( arr: &[usize], find: usize) -> Option {
   let length = arr.len();
   let mut half = length / 2;
   let mut hind = length - 1;
   let mut lind = 0;
   let mut current = arr[half];

   while lind <= hind { match current.cmp(&find) { 
            std::cmp::Ordering::Equal => return Some(half),
            std::cmp::Ordering::Less => lind = half + 1,
            std::cmp::Ordering::Greater => hind = half - 1,
        }
        half = (hind + lind) / 2;
        current = arr[half];
   }
   return None;
}

This revision gives us a function that is easy to read while using some built-in Rust functionality. This will also make it easier to extend the function to generic types in the future.

Learning Rust

This project taught me a lot about Rust’s syntax. I had the opportunity to fight with the compiler because of mismatched types, read foreign stack traces, and feel the reward of creating my first algorithm in Rust.

Interacting with the Rustaceans 🦀 was also a blast. I reached out with questions to the community, and they helped me analyze my problem while giving me suggestions on how to make my code Rustier. Having a great community makes me even more excited to continue forward with my learning!

To be continued

I plan to continue spending time learning Rust because I had so much fun with the language! I plan on extending this algorithm to handle generic types and then pivoting to implementing trees in the future!