Quick Overview of Binary Search
get familiar with this popular algorithm
While working to secure a software engineering role, algorithms are unavoidable. Especially when it comes to the technical interview. To better prepare, one of the things I have been doing is spending countless hours on LeetCode solving my way through the 1747 problems. It can feel a little overwhelming at times, but thankfully there are a handful of algorithms that frequently come up in the interview setting to focus on. One of them being the binary search algorithm.
This is an algorithm whose time complexity is O(log n) or in the best case scenario, O(1), when the target value is exactly at the center index. Because we figure Big O Notation based on the worst case scenario, we should assume that its complexity is O(log n) when discussing.
When searching for a specific value in a sorted Array- the binary search is optimal to the standard, Linear Search, whose time complexity is O(n).
Okay, but how does this thing work?
Looking at the example above, we see that our target value to find is 9. The top array of numbers is using the binary search, which we will focus on.
To solve, let’s begin by naming a few pointers- start ( being placed at index 0), end (points to the last index of the input array, so array.length-1) and then the middle pointer. The formula to figure the midpoint of the given input array is:
middle = start + ( end — start ) / 2
Looking again, at the above example & applying the midpoint formula, our middle pointer lands at 5. Because this is a sorted array we can check the value at the midpoint against the target value to know which way to look. In this case 9 > 5, so we know we need to look to the right side of the array. We then ‘move’ our start to the center and recalculate the new midpoint.
The new middle is the value 7, and again we check this against the target value. 9 > 7, so again, we look to the right. After updating start to the index of the 7, refigure middle and check the value against the target value. 9 > 8, so we move the middle to the last remaining index to the right and viola- our target value!
This isn’t a great example because the target value was at our end pointer from the beginning, which we can include in our conditionals. I chose this animated example because it clearly shows the time difference between using binary search and linear search to solve the same problem.
Now when you’re digging deep into LeetCode’s crates of algorithms, when you come across a sorted array or are asked to search for a target value in a given array, think binary search! Even if it’s not your first solution- it’s a great way to optimize.
Please feel free to leave any questions or comments below about binary search, your experience with LeetCode, technical interviews, etc. You can also follow my journey on LinkedIn and connect further.
