Searching Algorithms for Dummies: Binary vs. Linear
Whether you’re an experienced computer scientist or a novice developer, the word algorithm is something you may have already heard of. The Introduction to Algorithm textbook by CLRS (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein) defines an algorithm as:
“…any well-defined computational procedure that takes some value or set of values as input and produces some values or set of values as an output”
Algor-what?
Algorithms are essentially the steps that convert a given input to a desired output. These algorithms will become an integral part of your software developer career. If you are currently preparing for a technical interview or studying computer science, you will come to discover the importance of search algorithms. Why are searching algorithms popular? Well they do one thing and it is to obtain an element from a data structure — quite useful right? Well despite the countless numbers of searching algorithms, the most popular ones and often taught at the beginning of a developer’s journey are linear and binary search. The goal of this article however is to discuss the differences between two of the most popular search algorithms, their use cases, and their respective space & time complexities.
Linear Search
For linear search, it is rather simple. You are given a set of data, let’s say within an array and your goal is to search for an item in a list. This works whether the array is sorted or not sorted because you are iterating through every individual item until you find the item you are searching for.
Pseudocode
- iterate through each item in a list
- if the item iterated upon matches the sought after value
- return the location of the item
- otherwise if no matches are found
- print item not found
Binary Search
Binary search on the other hand is a little more tricky than linear search. Unlike linear search, binary search has one crucial pre-requisite. That one pre-requisite is that the data to be searched, MUST BE SORTED. If not, binary search is unfortunately not possible. The reason why a sorted array is necessary is that there is no median value to cut at. This basically means you cannot isolate either half of unnecessary values to quickly narrow down your items to search through. The best way to imagine this is with a phonebook. Now that we have covered the pre-requisites for a binary search, lets dig deeper into how it actually works.
Imagine a student directory — a book filled with all of the names of the students that attend a school. Usually if the school knows how to create a directory, it is SORTED in ALPHABETICAL order so that anyone who may try to find a name, can do so at ease.
Let’s say you are looking for the name: Bugs Bunny. You know that the last name “Bunny” is towards the beginning of the alphabet. You would probably open the directory towards the beginning of the book right? You would probably open the directory and skim through the first half because it would only make sense to look towards the front for “B”.. Now imagine if you have to look for Spongebob Squarepants. You know that the last name “Squarepants” is towards the end of the alphabet, so naturally you would look at the end of the directory for that name and open the directory in the second half.
This is essentially the foundation of binary search. You take a sorted set of data and constantly divide the set in half based on whether or not the value to be searched is less than or greater than the middle of the dataset. You would continue to do this until the item is found or there is nothing left to divide, thus returning nothing.
Now imagine a book with names jumbled everywhere with no order — wouldn’t that take ages to find a specific name? You could constantly open it up at random spots and guess, but it would probably be best to go through each name from start to finish. That’s binary search in a nutshell for you — not as fast as Linear.
Pseudocode
- If the starting index is greater than the ending index
- Return false
- Divide the sum of the starting index and the ending index by two, then set that result to mid
- If the element is found at the mid index of the array
- Return true
- If the element is less than the mid index element
- Call binary search on all items before the mid index
- Otherwise, call binary search on all items after the mid index
Binary Search vs. Linear Search
Although linear search algorithm is the most fundamental search algorithm and probably the first that most developers will learn, Binary on the other hand is the one that many will think of using when interview questions are brought up. To no surprise, binary search algorithms are indeed one of the most popular concepts that every computer scientist should know. The reason for this is quite simple. It is one of the most efficient search algorithms when looking for an element from a large amount of data.
Think of when you’re looking for a user on Facebook. As of April of 2019, there are 1.74 billion mobile active users (Zephoria). Now imagine how long it would take to search through all of those users to find that person you entered into the search bar. If you were to search through that large amount of data with linear or sequential search, in the absolute worst case, you would have to go through all 1.74 billion users — something that would take way too long. However, with Binary Search, the amount of time that can be saved is staggering. You are literally removing half of the potential options with each iteration.
// Time ComplexitiesLinear Search- Best Case: O(1)
- Average Case: O(n)
- Worst Case: O(n)Binary Search
- Best Case: O(1)
- Average Case: O(log n)
- Worst Case: O(log n)// Space ComplexitiesLinear Search
- Worst Case: O(1)Binary Search
- Worst Case: O(1)
Linear search at its very best case is O(1) due to the fact that if the first index is match, it’s an instant find. However where the time complexities begin to grow very slow is when the size of the array grows larger and larger and where the item you’re searching for require you to traverse great lengths of the array. There is no jumping around with linear search, but to iterate one by one.
Binary search on the other hand allows for the best case to be O(1) similarly to linear search where when split in half, the mid-point is an instant match. Where binary search at its worst becomes O(log n) is due to the fact that whenever we cut the size in half, we eliminate half of the unnecessary values. By halving for every iteration, that is how O(log n) becomes the average/worst case time complexities.
Linear search fails to be practical, albeit simple for new developers to understand searching. Binary on the other hand, which takes a little more to wrap you head around can be very fast compared to linear. However it does have its own pitfalls such as having to be sorted.
