In binary search, we need an array of integers for it to search for an element. Also, many other sorting algorithm sorts array of integers.

But in real world, we may search for a name of an employee in a database, title of a post etc. So how does binary search actually works in such cases? Is the data converted and stored in some numeric format? Then how does it point to the original record?

Please explain in detail with a small example if possible.

  • 9
    Binary search has nothing to do with integers. It applies to any ordered domain. I’m not sure where you got this misconception from. – Yuval Filmus Dec 2 at 7:06
  • In a sense, you are right: in a real computer, all data boils down to integers with some limits (as strings of bits). But algorithms per se usually don't have such restrictions. – Kirill Bulygin Dec 2 at 16:14
  • “Is the data converted and stored in some numeric format?” Well, yes. Computer memories only store bits, everything else is defined by data formats "we" invented. You might want to check out how encodings such as ASCII work. – Andrea Lazzarotto Dec 4 at 17:34
up vote 8 down vote accepted

As Prof. Filmus said, it isn't necessary for Binary Search Trees (hereafter referred to as BST's) to necessarily have ints/Integers as the data within the nodes.

At least in Java, all we need is data that is either Comparable to itself or some superclass of itself (implementing Comparable) or can be compared with an outside tool (using a Comparator). But I digress, as that is language-specific. It should be clear however that we only need elements to be comparable/order-able. They do not only need to be integers.

You could always, theoretically, use BSTs to model decision making, as you're simply going through Decision A or Decision B at any given point. You'd have to create Decisions that were comparable to one another, but that's fuzzy on my end.

Let me therefore take an example in your post - searching through a database for a name. Of course, names are usually encoded as Strings (a sequence of characters, informally speaking). Strings are usually ordered lexicographically, that is, by alphabetical order. This means that to retrieve a given String from a BST of Strings, we'd start at some root node which contains a root String (consider a String of this database in the M or N range, as that is the middle of the English alphabet), and if the name comes after M/N or before M/N, it will go to the right node or the left node of the root node (containing the middle name), respectively.

Theoretically, you could encode the entire English lexicon into one very large BST, if you have a word that you've set as the exact middle of the English language. Every word that isn't the exact middle word would be coming after or before said word, alphabetically speaking.

I'd point you to this link, about Legislation perhaps being NP-Complete, for some discussions about decision trees. This may be an interesting, albeit not necessarily appliable analogue with BST's: Is legislation NP-complete?

Hope this helps!

EDIT: Edited to say "Prof. Filmus..." as that is more formal.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.