In our everyday lives, we certainly have and will do the task of searching for things, like concrete objects, names in a phone book, books in a library, utensils in the kitchen, and many others. The task of searching for humans is indeed not a problem, as most of us are inherently equipped in doing such a task.
When it comes to computers, searching is a task found in many programs and applications our lives depend on. For example, looking up names on our Contact App, searching for games in the App Store, finding friends on Facebook, you get it. We sometimes take this feature for granted, without thinking about how its methodology is implemented.
Let’s take a step back and discuss the possibilities of how different search algorithms might work and further down we shall see how each of them performs compared to another. Do understand that there isn’t “the fastest search algorithm,” nor are they all comparable to one another – let’s see why.
Linear Search
First up is perhaps the easiest, most intuitive way of searching for things. Linear search, like its name suggests, is the act of looking sequentially, hence linearly. An analogy for this is, say, you have a row of unsorted books in a book store. Suddenly, a customer comes in and asks you whether a book titled “Harry Potter and the Philosopher’s Stone” is available.
Since the row is unsorted, a linear search may just be your only option. That is, you start from the beginning of the row, see whether the book is indeed titled “Harry Potter and the Philosopher’s Stone.” If it is indeed the book the customer is looking for, your task is done! Otherwise, you continue to the adjacent book, compare its title, and repeat the process until either you’ve found the book or find out that the book is unavailable and cause the disappointed customer to walk away with sadness.
That’s it, that is a linear search! It’s quite easy and intuitive to do, including in other real-world scenarios. Lost your phone somewhere in the house? Well, check every corner of the house to find it! As easy as that.
In the case of computers, the most basic form of a “collection” of data is called an array, which is named almost literally when you say “an array of objects” in a day-to-day conversation. So, if a programmer stores a list of names in an unsorted array, and he/she is given a task to find whether “Bob” is existent in the array, he/she can simply use linear search.
Given how the algorithm works, how well does it actually perform? Though it is easy to do and implement, a linear search is relatively slow. Say you have N number of books in the bookstore. When you tried to look for “Harry Potter and the Philosopher’s Stone,” you had to search one book after the other.
If you’re lucky, you can, to your surprise, find the book in your first lookup, i.e. it is the first book in the row. However, what happens when you go through all the lists and realize that the book isn’t present, or that it is the last on the list? Well, you have met the worst-case scenario of linear search as you had just looked through all N books in the bookstore.
Computer scientists have long developed a measure of algorithm performance, one of which is time complexity: the number of operations they take. They like to group them based on its worst-case scenario, average-case scenario, and best-case scenario.
A linear search is said to have a worst-case time complexity of 
Binary Search
Now, let’s twist the case a little bit. What if books in the bookstore are all sorted alphabetically? What can we do differently this time, now that we have a sorted list? Certainly, we can always do a linear search, but as we’ve discussed, it’s definitely tiring to look through all books while you can optimize better given additional prior information.
A popular search algorithm to use on sorted data is called the binary search algorithm. Here is how you might implement it in the bookstore case. Now that all books have been sorted alphabetically, it would be wiser to start at the center of the list, which you can estimate it to be books which start with the letter M since M is the center of all 26 English alphabets.
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Then, you have two options: to either go left or to go right. Think about it, you’re looking for “Harry Potter and the Philosopher’s Stone” whose title starts with the letter H. As you know, H comes before the letter M, so you can move to the left of books starting with M, and continue your search from there. Again, you find the new center of the left half of the books, which in this case are books that starts with the letter G, as G is the middle between letters A and M.
A B C D E F G H I J K L M
Repeat the process, are books which start with the letter H placed on the right of books starting with G, or are they located somewhere on the left? Well, since comes after G, you continue your search on the right half.
H I J K L M
Now, the middle letter between letters H and M is J, so you make another comparison. H comes before J, so you now look to the left of books starting with J.
H I J
Then, between letters H and J lies the letter I, so you make another comparison: does H come before I, or after I? Of course, H comes before I so you turn to the left neighbour of I, where you can only find the required letter H.
H
Though it sounds complicated and unintuitive, binary search is faster than a linear search. It is because if you’ve found the center of the list, and chose to either go left or right, you’ve ignored the second half since you’re 100% sure that there won’t be books starting with the letter H!
Unlike linear search, binary search keeps halving the list and thus prunes the need to go through every single book in the bookstore, granted that books are sorted.
Prior knowledge of how a collection of data is arranged is indeed a fact which algorithms can exploit. Search algorithms may not always be comparable to another as one may have a different set of conditions to be able to run, like how binary search depends on a sorted list. If your list is unsorted, then binary search is of no use! You can’t find a logical center point since there isn’t one.
In terms of time complexity, a binary search is said to have a worst-case of 
Other Search Algorithms
We’ve only introduced two search algorithms, but there are tons of search algorithms available. Nonetheless, each of them may require different dependencies, like knowing certain apriori knowledge of how the data is arranged. Hence, they are incomparable to one another, for the most part, although one can always measure their time complexity to get a feel for the speed-up.
Moreover, several search algorithms may have an entirely different purpose. The ones we’ve discussed above are basic searching algorithms, i.e. when you have to look for the existence of the desired object. Other usages of search algorithms include finding the shortest path from one point to another, traversing through graphical representations, getting the solution to an equation, deciding on a game’s next best move, and so on.
Likewise, some search algorithms rely on specific data structures, that is, how data is stored in memory. An array is a trivial example of a data structure, where objects are stored sequentially. Similarly, there are other data structures like graphs, trees, hash sets, dictionaries, linked lists, and more. At times, search algorithms exploit how data are stored in such data structures and could thus reach a more optimal time complexity thanks to that.
Closing Remarks
So, are we on the search for a better search algorithm? Well, we sure are. Maybe we won’t find a faster way of looking through an unsorted list of arrays, but we certainly can store them differently such that we can attain faster time complexity, given a special data structure.
Now that you’ve understood how one can measure the speed of search algorithms, how they are possibly incomparable to one another, and how data structures could be beneficial for searches, you can safely say that you know a fundamental, yet important, intricate knowledge in the huge field of Computer Science.
Perhaps when you walk into a bookstore and would like to find a textbook about algorithms, you can do a human-level binary search yourself! But remember, make sure that you ask a store employee whether the books are sorted!
Featured Image by Pixabay.
