Searching Algorithms: Binary Search

(Javascript implementation)

Binary Search Algorithm

This search algorithm works on the principle of divide and conquer. For this algorithm to work properly, there is a big caveat: the data collection must be sorted.

Time complexity:

• Worst and Average Case: O(log n)
• Best Case: O(1)

How Binary Search Works?

Binary search is going to compare the element we are looking for with the middle element of the collection. If there is a match, it will return the index of the middle item. If the middle item is shorter than the item we’re looking for, we forget about the sub-array from the middle to the right, and repeat the operation searching for the sub-array to the left to the middle item.
We continue this process until find the item or until the size of the sub-array reaches 0.

Let’s try to understanding it by looking the algorithm step by step:

Let’s look for the number 9 in this array.

First, we need to set the middle point (orange) by averaging the sum of the start(green) and the end (red).

Since 9 is greater than 5 we forget about smaller numbers and create a new search in the right sub-array.

9 was greater than 7, so we repeat the previous operation and since 9 is the item we were looking for. We return the index.

Pseudocode:

// Write a function that accepts a sorted array and a value.
// Create a left pointer at the start of the array and a right
   pointer at the end.  
// While the left pointer comes before the right pointer:
// Create a pointer in the middle
// If you find the value you want, return the index.
// If the value is too small, move the left pointer up.
// If the value is too large, move the right pointer down.
// Return -1 if the value is never found.

Code: