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

1. Determine the index of the middle element if length is odd or the lowest of the pair of middle elements if length is even.
2. The mid index is ⌊(high - low) / 2⌋ + low.
3. Compare the value at this index with the target.
4. 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
5. Keep doing steps 1 to 5 until the value of low is greater than that of high.
6. 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;	
}