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.
Binary Search can only be applied on the list which is sorted.
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
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
Binary Search implementation in Rust via Recursion