Part 8 — Data Structures and Algorithms in Plain English | String Binary Search

Hello there and welcome back from the long break session. In the last part, we talked about Recursive Binary Search where we discussed the very concepts of Binary Search we covered in part 5 along with the concepts of recursion in we covered in part 6.

If you have ever read an article about Binary Search, then I’m quite sure that the implementation would have made use of numbers. You check if the number is greater or lesser and proceeded to either the left or right array as necessary. But what if you have to search through strings? How do you perform mathematical comparisons on string data types?

Like you, I also asked this same question which is why I figured it’s essential we cover this part of Binary Search in our series. First, let’s start with an explanation of the concept behind how this will work.

Let’s say we have two strings, one string being abc and the other being def. How do we decide which string is greater? After all, that’s the necessary principle required for Binary Search to work. Well, comparing strings requires that we make use of a method called Lexicographical Ordering. Now, you begin to wonder, what is Lexicographical Ordering?

Lexicographical Ordering is the arrangement of words in the order with which they appear in the dictionary.

This ordering depends on the ASCII (American Standard Code for Information Interchange) encoding of common characters. So, whichever string has a lesser ASCII value is counted to be the smallest, and the one with the higher ASCII character is chosen to be the largest.

There, in the case of our string samples above, abc is lesser than def. However, ABC is greater than def. This is because strings in capital letters have higher ASCII values compared to those in small letters.

Now, let’s say we have a sorted array of strings (remember that Binary Search only works on sorted values) stored in a variable wordlist, we can write the String Binary Search algorithm in Python as given below.

Notice that there’s actually nothing different in the algorithm when compared to your previous knowledge of Binary Search on sorted numbers? This is because Python internally provides support for the comparison of strings using the Lexicographical Ordering we discussed above.

But in the case of JavaScript, the algorithm will come out a little different with the introduction of something called localeCompare. A String method that indicates whether a reference string comes before, or after, or is the same as the given string in sort order.

In JavaScript, our algorithm will become…

And there you have it! Binary Search on strings. Now that we have this sorted out, let’s actually take the coming parts of this series to look into how sorting algorithms work, the common types we have, and how we can write our own sort function.

And if you would love to get started in tech at any point in time, do check out https://cholatrek.io for an inclusive and streamlined learning experience.

Till then, stay safe 👋