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

Each recursive call:

• keeps half of the elements (remaining)
• 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":

/* Even */
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 

/* Odd */
const oddItemsArray = [1,2,3,4,5,6,7];

// length = 7
// length/2 = 3.5

// index = floor(length/2) = 3
// value at floor(length/2) = 4 // middle

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

Recursive Implementation