In computer science, few tools are used quite as often as search algorithms. We rely on them every day as programmers and engineers to sift through data, and they're built into nearly every modern programming language in one way or another.
One of the most important and widely used search algorithms is known as a Binary Search, also known as a half-interval search, logarithmic search, or binary chop. Wikipedia describes the function of a Binary Search as follows:
Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.
Essentially, what we're doing is breaking down the array we're searching through by half each time we iterate our loop, looking at that midpoint, and then comparing it to the target to see if we should break the array by half again to either the left or the right. Following that, we increment or decrement left and right pointers to shrink our window. To visualize it, let's look at an example:
array = [0, 2, 4, 7, 8, 10, 12]
target = 4
\/ midpoint, not target
[0, 2, 4, 7, 8, 10, 12]
^ left ^ right
\/ new midpoint, not target
[0, 2, 4, 7, 8, 10, 12]
^ ^
\/ new midpoint, target!
[0, 2, 4, 7, 8, 10, 12]
^
This might seem a bit odd at first, but it will quickly make sense the more you consider it (and once we put it into code.)
The key to Binary Search working the way it does, is knowing that the array of integers that we're working in is sorted. This is a necessity, since we're comparing each midpoint to the target and making an assumption that it will be to the left or the right properly when sorted ascendingly.
While this limits opportunities to use Binary Search somewhat, it's often the absolute best search to use when working with sorted data. As a result of its breaking-down-by-half of the array, Binary Search has a best case runtime complexity of O(log n), which is solid as far as search optimization goes.
Time to implement it!
Implementing a Binary Search algorithm is actually quite simple, relative to understanding the core logic, and can be done in as few as 14 or less lines of code.
Let's build it together, line by line!
First off, we'll declare the function and its parameters:
function binarySearch(arr, target) {
}
Next, we'll define our left and right pointers with their initial values. The left pointer will start at the beginning of the array, and the right pointer will start at the end:
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
}
Now we add the core piece of logic for the function: a while loop. This while loop will be comparing the values of the left and right pointers, continuing to run as long as the left is less than or equal to the right.
Essentially this will tell the loop to run until our window is "closed", meaning we broke our array down as small as we could and still couldn't find a target value. We'll add a return value after the loop for this case:
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
}
return "Target Not Found"
// could also return -1, false, undefined, etc
}
Now we'll work on the loop. First off, we'll declare our midpoint variable and calculate its value, then add our "base case" which will return a value and end the function if the target is found:
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
}
return "Target Not Found"
// could also return -1, false, undefined, etc
}
In this version of the algorithm, we're simply returning the index of the target value if it has been found in the array. This return value could be changed to whatever you prefer.
And last but certainly not least, we'll implement the if else statement that checks whether the target is to the left or right of the midpoint, and increments or decrements the pointers accordingly:
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (target < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return "Target Not Found"
// could also return -1, false, undefined, etc
}
And we're done!
The above code is the finished algorithm, which can be implemented anywhere and everywhere it's deemed appropriate.
Many programming languages have Binary Search built into their syntax, or provide options to implement it more easily, but understanding the core logic of how it functions by breaking down the array into smaller sections and comparing values is incredibly important for technical interviews and for designing your own algorithms to solve specific problems.
If you've come this far, thanks very much for reading! :) I'll continue putting out more tutorials and deep dives on the things I'm learning as a programmer as I go along.
Top comments (0)