Binary search is an important search algorithm. It is an efficient method to search for a specific element within a sorted array. While it’s a pretty simple and intuitive concept, it is a powerful tool and one worth getting deeply familiar with.
Conceptual Overview
Binary search works by taking in an array sorted in ascending order and determining the middle element of the array. It then compares this middle element to the element you are searching for. If the element you are looking for happens to be the middle element of the array, then you’ve found the element in O(1) time. If the middle element is not the target element, we then compare this middle element to the target element. If the target element is smaller than the middle element, then we know the target element is in the first half of the array, so we can safely eliminate the second half of the array starting from the middle element. Conversely, if the target element is bigger than the middle element, we know the target element is somewhere within the second half of the array, thus we can eliminate the first half of the array starting from the middle element.
We then continue this process with the remaining elements in our array until we eventually find the target element or we have eliminated the whole array (at which point we know the element is not in the array). At each iteration, we eliminate half of the remaining elements, so you can imagine that this algorithm works quite quickly. Binary search allows us to perform a search function in O(log(n)) time in the average and worst case scenario.
Real Life Example
While you might not have known what binary search is by name, chances are, you’ve implemented it in some form or other in your daily life. Let’s pretend you’re a teacher and you’ve just given an exam. You have now collected all of the exams and have sorted the papers in alphabetical order by the student’s last name. Let’s say that you now want to find a specific student’s exam in the pile so you split the pile of papers roughly in half and look at the last name. If the last name you’re looking for begins with a letter that comes later in the alphabet, then you know their paper is in the second half of the pile. You could then continue with this process with the second half of the pile, each time eliminating one half of the pile until you find the student’s exam.
Coding Walkthrough
Now that we understand the workings of the binary search method, we can begin implementing it.
Let’s write a function, binarySearch() that takes in a sorted array and a target element. We can start by having two pointers. One at the 0 index of the array and one at the very last element of the array. We then find the middle index by adding the leftIndex and rightIndex together and then dividing the sum by 2, remembering that indexes have to be whole numbers, so we then round down to get our middle index. We then look at the value of the element at the middle index and compare it to our target. If the value of the current element is larger than the target, we then move the right index to the left of the middle index. If the value of the current element is lower than the target, we move the left index to the right of the middle index. We repeat this process as long as the leftIndex is equal to or less than the rightIndex. If we find a match, we return the value of the middle index. If not, we return -1.
