# Binary Search in Rust

Rust, algorithms

Binary search is an algorithmically efficient way of searching an ordered array. It works by comparing the target value with the middle element of the array. If the two are not equal, the array is partitioned and re-searched, this time excluding the elements that are either too high or too low.

For example, if the target value is 42, and the middle element of an ordered array is 100, the target cannot lie in the elements from the mid point to the end of the array. This allows us to reset the search bounds, eliminating half of the previous array at each step.

## Binary search in Rust: Iiterative

Arguments: Array slice, array length, target integer to look up.

The initial value for `low`

(index of the first array element) is 0.

The initial value for `high`

(index of the last array element) is length - 1.

### Algorithm

- Determine the index of the middle element if length is odd or the lowest of the pair of middle elements if length is even.
- The mid index is ⌊(high - low) / 2⌋ + low.
- Compare the value at this index with the target.
- If the values are the same, return the index.
- 4a. If the target > value, search elements at higher indices (because elements indexed by these have higher values). Set low to mid + 1
- 4b. If the target < value, search elements with lower indices (these have lower values). Set high to mid - 1

- Keep doing steps 1 to 5 until the value of
`low`

is greater than that of`high`

. - If the function has not returned an index by this point, the returned option will be
`None`

.

To fully search the array, the type of the `high`

variable be such that the variable can hold a negative value.

## Rust

Rust is really strict about types and casting - there is no implicit type conversion between primitives.

Because of this, and the fact that `high`

must be able to handle negative numbers, computing `mid_index`

firstly involves manipulating `i8`

integers to perform the arithmetic, before overtly casting the result into a `usize`

type that can be used to index the array.

Note that the `Option`

type is ideal for the function return value - it allows us to return (and handle) a `None`

option if the target does not exist in the array. In languages without this capability, we might return -1 to indicate non-membership of the array - but this is not as overtly descriptive as `None`

!

## Code

The example below also includes a couple of tests.

```
// Binary search, iterative.
// Arguments: Array slice, array length, target integer to look up.
pub fn iterative(a: &[i32], len: usize, target_value: &i32) -> Option<usize> {
let mut low: i8 = 0;
let mut high: i8 = len as i8 - 1;
while low <= high {
let mid = ((high - low) / 2) + low;
let mid_index = mid as usize;
let val = &a[mid_index];
if val == target_value {
return Some(mid_index);
}
// Search values that are greater than val - to right of current mid_index
if val < target_value {
low = mid + 1;
}
// Search values that are less than val - to the left of current mid_index
if val > target_value {
high = mid - 1;
}
}
None
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn correct_iterative() {
let correct_arr = [
1, 10, 20, 47, 59, 63, 75, 88, 99,
107, 120, 133, 155, 162, 176, 188,
199, 200, 210, 222
];
for i in 0..correct_arr.len() {
assert_eq!(i, iterative(&correct_arr, correct_arr.len(), &correct_arr[i]).unwrap());
}
}
#[test]
fn incorrect_iterative() {
let searched_arr = [
1, 10, 20, 47, 59, 63, 75, 88, 99,
107, 120, 133, 155, 162, 176, 188,
199, 200, 210, 222
];
let incorrect_arr = [
2, 22, 48, 58, 61, 73, 84, 90, 100,
119, 132, 154, 160, 177, 187, 197,
201, 211, 2242
];
for i in 0..incorrect_arr.len() {
assert_eq!(None, iterative(&searched_arr, searched_arr.len(), &incorrect_arr[i]));
}
}
}
```

Calling code:

```
fn main() {
let arr = [
1, 10, 20, 47, 59, 63, 75, 88, 99,
107, 120, 133, 155, 162, 176, 188,
199, 200, 210, 222
];
let target: i32 = 47;
if let Some(result) = rust_binary_search::iterative(&arr, arr.len(), &target) {
println!("{} found at index {}", target, result);
} else {
println!("{} not found.", target);
}
}
```

## Similar Functionality in C++

Note that it returns -1 if the target value is not found in the array.

```
// Iterative algorithm: binary search
// 1. Set values for low and high indices - starting condition, low == 0, high == len -1.
// 2. Determine the mid index (or leftmost mid index if length is even)
// 3. If value at the mid index == target value, return the index.
// 4. If value at the mid index > target value, make a partition of elements with indices < mid index.
// 5. If value at the mid index < target value, make a partition of elements with indices > mid index.
// 6. Repeat until:
// - low > high
int binarySearchIterative(int A[], int len, int targetVal)
{
int high = len - 1;
int low = 0, midIndex = 0;
while (low <= high) {
midIndex = ((high - low) / 2) + low;
int val = A[midIndex];
if (val == targetVal) {
return midIndex;
}
if (val > targetVal) {
high = midIndex - 1;
continue;
}
if (val < targetVal) {
low = midIndex + 1;
continue;
}
}
return -1;
}
```

comments powered by Disqus