Binary Search in Rust, Python

Binary Search divides the sorted list into two halves, discards the half where our element can’t lie, and then repeats this until the element is found, or there is no half left to discard.

Pre-Requisite

Binary Search can only be applied on the list which is sorted.

Approach

Compare the middle most element in the list with the element you are looking for
If the match occurs, return the index of this middle element
If the element is greater than the middle element, then the element will exist in sub-list to the right of the middle element. Or else in the sub-list to the left of the middle element. (Why? Because the list is sorted)
Repeat these steps on the sub-lists until the element is found or else the sub-list becomes empty

Complexity

Since you are dividing the list each time reducing number of elements by half, the maximum time to find this element will be logarithmic time (with base 2),

O(log(n)), where n is this number of elements in the list.

Binary Search Implementation in Rust

Let’s look at two ways to implement binary search

via Recursion

Binary Search implementation in Rust via Recursion

 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
  fn binary_search<T>(
      list: &Vec<T>,
      start: usize,
      end: usize,
      element: &T
  ) -> Option<usize>
  where
      T: PartialOrd,
  {
      if end >= start {
          let mid = (start + end) / 2;

          match list.get(mid) {
              Some(x) => {
                  if element > x {
                      return binary_search(list, mid + 1, end, element);
                  } else if (element < x) {
                      return binary_search(list, start, mid - 1, element);
                  } else {
                      return Some(mid);
                  }
              }
              None => {
                  return None;
              }
          }
      }
      return None;
  }

via Iteration

Binary Search implementation in Rust via Iteration

 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
  fn binary_search<T>(
      list: &Vec<T>,
      mut start: usize,
      mut end: usize,
      element: &T
  ) -> Option<usize>
  where
      T: PartialOrd,
  {
      while end >= start {
          let mid = (start + end) / 2;

          match list.get(mid) {
              Some(x) => {
                  if element > x {
                      start = mid + 1;
                  } else if element < x {
                      end = mid - 1;
                  } else {
                      return Some(mid);
                  }
              }
              None => {
                  return None;
              }
          }
      }
      return None;
  }

Running tests

Add below tests to your file:

 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

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_search_success_found() {
        let mut example_list: Vec<i32> = vec![2, 41, 1, 65, 7, 8, 54];
        example_list.sort();
        assert_eq!(
            binary_search(&example_list, 0, example_list.len(), &7),
            Some(2)
        );
    }

    #[test]
    fn test_search_success_not_found() {
        let mut example_list: Vec<i32> = vec![2, 41, 1, 65, 7, 8, 54];
        example_list.sort();
        assert_eq!(
            binary_search(&example_list, 0, example_list.len(), &20),
            None
        );
    }
}

Run following to run the tests (remove --test to run the code):

1
rustc binary-search.rs --test; ./binary-search

Binary Search Implementation in Python

Let’s look at two ways to implement binary search

via Iteration

Binary Search implementation in Python via Iteration

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def binary_search(self, nums, start, end, element):
    while end >= start:
        mid = int((start + end) / 2);

        if element > nums[mid]:
            start = mid + 1
        elif element < nums[mid]:
            end = mid - 1
        else:
            return mid;

    return None;

Check out this Visualization and Wiki Link for more details.

Additional info

Rust has in built binary search methods which are available in Rust’s Vec type, see vec’s binary_search.
Binary Search is an example of Divide and Conquer algorithm.
Binary search tree and B-tree data structures are based on binary search.
Variants of Binary Search: