Abstract

Binary Search is one of my favourite searchin algorithms, it is quick and efficient most of the times to search, given a sorted array.

This is an implementation of this algorithm in Rust. This post marks the start of my Rust learning journey. Implementing this algorithm is a must and this allows me to learn the Rust syntax given a familiar algorithm.

In this implementation, a vector is used instead of an array, this allows for dynamic memory allocation of a given list of sorted numbers.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


fn main() {
    let vec = vec![1,2,3,4,5,6,7,8,9,10];
    let val = 3;
    let pos = binary_search(vec, val);

    if pos != -1 {
        println!("{} is at position {}", val, pos)
    } else {
        println!("{} is not in the vector", val)
    }
}

fn binary_search(vec: Vec<i32>, val:i32) -> i32{
    let mut left:i32 = 0;
    let mut right:i32 = vec.len() as i32;
    let result = -1;

    while left <= right {
        let mid:i32 = (left + right) >> 1;

        if vec[mid as usize] == val {
            return mid;
        }
        else if vec[mid as usize] < val {
            left = mid + 1;
        }
        else{
            right = mid - 1;
        }
    }
    result
}

Output:

1

3 is at position 2

Similar to the previous implementation of Binary Search, I used the right shift >> 1 to do the division by 2 to get the mid value, followed by the iterative version of the comparison.

Rust Binary Search

Abstract

Code