Binary Search

Searching in a sorted array or a binary search tree (BST is a sorted data structure) is way more efficient because we don’t have to look at all elements.

We can design some logic to look at only some of them quickly. Because elements are sorted, we can split elements into two parts; that’s why it’s called binary.

This is the code for a binary search on an array:

If the array is nil, we can immediately return nil as the value is not present.

We define a window with the left index at 0 and the right index to the last element of the array; then, we loop until the window becomes empty (left greater than right). For each loop run, we define the middle index (between left and right) and check the element at this index. If the element is lesser than the given value, we make the window start after the middle index; if it is greater, we make the windows end just before the middle index, and if it is equal, we find the searched element we return the index. If the window becomes empty, we…