## Binary Search in Rust, Python

### What is Binary Search? Why to use Binary Search? How to implement Binary Search in Rust, and 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( list: &Vec, start: usize, end: usize, element: &T ) -> Option 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( list: &Vec, mut start: usize, mut end: usize, element: &T ) -> Option 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

 `````` 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 = 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 = 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; ``````

## More

Check out this Visualization and Wiki Link for more details.