How does binary search work?

When efficiency is the primary goal, binary search is utilized. It entails dealing with material that has previously been sorted in either ascending or descending order. The search begins with the centre element in the array, which is discovered first. The array is divided into two halves based on whether the search value is more than or less than the middle member. It’s crucial to understand the arrangement’s sequence in order to find the right value.

Think about how you’d search for a word in a dictionary. Looking at every word would be very slow, so you need a faster method. You’re probably going to open the dictionary roughly in half, look at a word and use the following procedure:

  • If it’s the word you want, then great!
  • If it comes before the word you want, you try again with only the right half of the dictionary.
  • If it comes after the word you want, you try again with only the left half of the dictionary.
  • If you’ve already seen the words at both sides, then the dictionary doesn’t have the word

Every time you do this, the number of pages you need to search is cut in half, so you’ll arrive at your word rather quickly.

There is one important drawback: you’re relying on the fact that the dictionary is sorted (ordered). If the words in the dictionary were in a random order, you’d be out of luck with this method.