What is binary search?

Binary search is an algorithm that finds the index position of a target number within a sorted array of numbers using a divide and conquer approach.

Why binary search?

The benefit of this algorithm is its speed at narrowing down which half of the array contains the target number. Therefore, as the input size—the length of the array that is being searched—grows, the time it takes to check for and locate the target number is more time efficient than a linear search of the array (which would check one number in the array at a time until it happens upon the target number).

Binary search has a logarithmic time complexity, or O(log n).

How does binary search work?

A basic binary search function takes in a sorted array of integers and a target number that you are trying to locate within the array. It will return the index of the target number if the array contains it.

View a recursive JavaScript function example »

For an array sorted from smallest to largest a binary search function will:

1) Identify the midpoint number that is located in the middle of the sorted array.

2) Compare that midpoint number with the target number it is trying to locate.
       a) If the midpoint number IS the target number:
             The function returns the index of that number.
       b) If the midpoint number is LARGER than the target number:
             The function recursively calls itself on the left half of the array and continues until the target is found and its index is returned or there are no more numbers in the array to search.
       c) If the midpoint number is SMALLER than the target number:
             The function recursively calls itself on the right half of the array and continues until the target is found and its index is returned or there are no more numbers in the array to search.