How does it work

Search algorithm applied to a sorted array by repeatedly dividing the search interval in half.

• In a sorted array of size n, binary search finds the element by repeatedly dividing the array in half.
• Repeated dividing of array in half makes is logarithmic.

You can NOT apply binary search on an unsorted array.

• One exception is a rotated array.

Side note

• if you "know" one side of the array is sorted, you can apply binary search on that specific half of the array (within that limit).

Logarithmic Time Complexity

In each recursive call, it keeps half of the elements (remaining) and eliminates half of the elements (discarded).

Hence, the time complexity for search is:

O(log n)

Implementation

Basics

Writing a binary search algorithm requires understanding of finding a middle of the array.

// round up
Math.ceil

// round down
Math.floor 

Finding the Middle

Synonymous to "finding the median":

const evenItemsArray = [1,2,3,4,5,6,7,8];
// length = 8
// length/2 = 4
// value at length/2 = 5 // right of middle two [x, right]
// value at length/2-1 = 4 // left of middle two [left, x]

evenItemsArray[evenItemsArray.length/2]; // 5 
evenItemsArray[evenItemsArray.length/2 - 1]; // 4 

const oddItemsArray = [1,2,3,4,5,6,7];
// length = 7
// length/2 = 3.5
// floor(length/2) = 3
// value at floor(length/2) = 4 // only middle

oddItemsArray[Math.floor(oddItemsArray.length/2)]; // 4

Recursive Implementation