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.

  • 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.
// 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.

Computer Science and Software Engineering