Binary Search

Today we'll talk about binary search, an algorithm that uses the divide and conquer strategy. This algorithm is one of my favorites, it's quite simple to wrap your head around, it's fast and it's short to implement but it has one major caveat, let's find out what it is!

The Divide and Conquer Strategy

So the divide and conquer strategy, what's up with that? Well, with binary search you define three pointers one of them is the middle pointer which allows you to split your input array into two smaller parts the left one with values smaller than the middle value and the right side with values greater than the middle value. From there you can check : is the middle value greater than the one I am looking for? If so, you continue by splitting the left array this time and again check is this new middle value greater than the value we are looking for? If it is we'll look at the right array and repeat the process until we find the value.

Also don't forget to check if the value is equal.

So this is great, instead of looping through each value we split the array a certain number of times until we find the value resulting in a interesting bigO notation of O(log n), that's great right? As I mentioned there is one caveat and you probably guessed it, the array we are looping through has to be sorted. Otherwise we can't know that the middle value we chose is greater than it's left value and smaller than it's right value so it could turn out to be really inefficient, even more than linear search.

That's why sorted arrays only! Now that we get that out of the way, how does it look like?

function binarySearch(sortedArr, value) {
  let start = 0;
  let end = sortedArr.length - 1;
  let middle = Math.floor((end + start) / 2);
  while (end >= start) {
    if (sortedArr[middle] === value) return middle;
    if (value > sortedArr[middle]) start = middle + 1;
    if (value < sortedArr[middle]) end = middle - 1;
    middle = Math.floor((end + start) / 2);
  }

  return sortedArr[middle] === value ? middle : -1;
}

Code Breakdown

1. Initialization: Define three pointers—start, end, and middle.
2. Loop: Continue as long as end is greater than or equal to start.
3. Comparison:

• If the middle value matches the target value, return its index.
• If the target value is greater than the middle value, adjust the start pointer to middle + 1.
• If the target value is less than the middle value, adjust the end pointer to middle - 1.

4. Update Middle: Recalculate the middle pointer.
5. Final Check: After exiting the loop, the last value could be the one we are looking for and our while loop explicitly excludes it (end >= start) to prevent running out of the array, so we conditionally return the index value or -1 if we didn't find anything.

Performance considerations

Binary search is highly efficient for large datasets due to its O(log n) time complexity. This means that as the size of the input array increases, the number of steps required to find the target value grows logarithmically (the growth rate slows down as the input size increases), making it much faster than linear search (O(n)) for large arrays.

However, it's important to note that the efficiency of binary search comes with the assumption that the array is already sorted. If the array is not sorted, you would need to sort it first, which typically has a time complexity of O(n log n). Therefore, for small datasets or unsorted arrays, the overhead of sorting might outweigh the benefits of binary search.

Additionally, binary search is well-suited for scenarios where you need to perform multiple searches on the same dataset. In such cases, sorting the array once and then performing multiple binary searches can be more efficient than repeatedly performing linear searches.

Conclusion

Binary search is a powerful algorithm that leverages the divide and conquer strategy to efficiently search through sorted arrays. Its logarithmic time complexity makes it ideal for large datasets, but it's important to remember that the input array must be sorted for binary search to work correctly.

Understanding when and how to use binary search can significantly improve the performance of your applications. So, the next time you need to search through a sorted array, consider using binary search to conquer the problem efficiently!

Happy coding ! 👨🏻‍💻