Idiomatic Rust? Implementing binary search

submited by

Style Pass

2021-05-29 13:30:05

The purpose of this algorithm is to determine if a given search value exists in a sorted array. You can read more about it on the wikipedia page and I've also created the following visualization to go with it:

As you can see from above, the implementation I chose uses a high and low cursor that begin at either end of the array. We then enter a while loop and find the middle point each time which is compared to the search target.

Seasoned Rust developers may notice something that I totally over-engineered here, mostly because of my background in JavaScript, let's take a look.

Part of this algorithm requires you to continuously find the mid-point between your remaining items - this becomes the new 'middle'. We do this by adding the high + low values, and then dividing by 2. so if high=5 and low=0, then its (5 + 0) / 2 = 2.5.

The issue here is that we need to use a whole number to perform the next lookup. We can't do items.get(2.5) as this just doesn't make any sense.