Searching Algorithms: Binary Search

(Javascript implementation)

Binary Search Algorithm

Time complexity:

How Binary Search Works?

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:

Computer Science and Software Engineering

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store