Algorithm Spotlight: Binary Search 🔎

Learn Binary Search in this exciting guide!

Last Updated: October 16, 2020

Source

Preface

Part 1: The Concept of Searching

Part 2: Binary Search 🔎

  1. Calculate the middle element’s index (low + (high — low) / 2 is preferred over (low + high) / 2 to prevent overflow). This value is typically named mid .
  2. Get the element at index mid and set this value as guess.
  3. Check through the following cases:
  • If the guess is the target value, then return the index found (mid ).
  • If the guess is less than the target value, the array from the index 0 to index low is “wiped out” as the target element is definitely not present in that interval. To “wipe out” and decrease the search space in half, we set low = mid + 1 for the next iteration’s middle element index calculation.
  • If the guess is greater than the target value, the array from high to the end of the array is “wiped out.” We then change high to high = mid — 1 .
Source

Part 3: Limitations of Binary Search

  1. The array must be sorted. Most programming languages have quick sorting algorithms that run in O(n log n) time. Even before Binary Search, the time complexity is even worse than linear time, which runs in O(n)!
  2. Binary Search only works on data structures that are indexed (e.g., array) or have direct access to elements. If we can’t directly access elements in data structures, we cannot apply Binary Search to it.

🎉🥳 Congratulations! Now that you understand the concept of Binary Search let’s move on to a more challenging problem!

Part 4: Find First & Last Position of Element in a Sorted Array

  • upper_bound(arr, x) — the index of the first item in the array arrthat is greater than target x
  • lower_bound(arr, x) — the index of the first item in the array arr that is equal to target x

Part 5: Practice Problems

  1. This problem is very similar to the original Binary Search implementation, except with a bit of difference. Click here to learn more about it.
  1. This is just the Binary Search problem in disguise.
  2. Implement Binary Search, except change the conditional statements to match the guessing game.

Thanks for reading and don’t miss out on the next episode of Algorithm Spotlight!

--

--

Planet Earth, The Milky Way, Local Group, Virgo Supercluster, Laniakea Supercluster, the Universe

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Aaron Ma

Planet Earth, The Milky Way, Local Group, Virgo Supercluster, Laniakea Supercluster, the Universe