- September 7, 2023
- Jhun Rey Castillo
- 0 Comments
The adjective “binary” means “Using or denoting a system of numerical notation that has 2 rather than 10 as a base”, and that is right, binary search indeed deals with “2”: it involves binary decisions with two choices at each step of the search, which means at each step of the search you can eliminate half of the amount of data. One typical example of this is searching a name in phonebook. If you are using linear search/sequential search, it means you will start from the first page, look for every name in the phone book until you find it. That way, the name you are looking for can be the first one on the first page if you are lucky, or somewhere in between page 1 and last page, or the worst case, the last one at the last page. Therefore the worst-case running time for a sequential search is always O (n).
On the other hand, binary search is just like what you will do in real life when searching for a name in phone book. Let’s say you are searching for the name “Walter”. You will just open the phone book approximately half way. OK, there are 26 alphabets, so in the mid way it mus be names start with the letter “M” (the 13th alphabet). Now you will think: OK, “W” in the word “Walter” is after the letter “M”, so it can’t be in the first half of the phonebook, so you “decide” to skip the first half of the phonebook and the result must be in the second half of the phone book. Now you flip the second half of the phonebook half way, it’s probably a name starts with the letter “T”. because letter “T” is in the middle of letter “M” and “Z”. Again, you will come up with the same idea to skip the first half from “M” to “T” because “W” isn’t there… Now only “T” to “Z” remains… You repeatly making this kind of “decision” to eliminate half of the remaining data, until you find the name “Walter” on the phone book.
If you are searching for a data entry in n pieces of data, after the first “decision” you eliminate n/2 of the total amount of data, second time you eliminate another n/2 of the previous n/2, meaning so far you have eliminated 3n/4 of the total amount of data. The 3rd time you eliminate another n/2 of the previous n/2 of its previous n/2, meaning so far you have eliminated 7n/8 of the total amount of data, and so on so forth. Therefore, the worst-case running time for a binary search is always O (log n), and that is much smaller than O (n), and therefore much faster than sequential search.