Algorithms 101: JavaScript Binary Search and It’s Big O Notation
Binary search is a commonly used algorithm offering a more efficient form of search than a traditional linear search. Instead of iterating through an array eliminating one element at a time, you can eliminate half of the remaining elements at a time. However, it only works with sorted arrays and ordered lists.
How It Works
A binary search starts in the middle of an array and checks if that value is greater than, less than, or equal to the value you are looking for. If that element is greater, the algorithm now knows to continue searching in the left half of the array among the smaller values. Remember, the array is sorted. If the element is less in value, the algorithm knows to targets the right half.
So, how does that actually work?
Let’s say you have an ordered array of 16 elements, and you want to know if the array contains the value 18.
“Pointer” variables are initially assigned to the first and last elements with a third assigned to an element that best represents the “middle” of the array. The algorithm will then assess this middle pointer for a match…