# 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 **middl**e 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.*