Searching a certain value in large datasets could be really tiring and time-consuming sometimes. Do you want to through all these one by one? Or are there any better options? In today’s post at algo.monster, we will talk about these two popular search algorithms: binary search and linear search.
When it comes to computer science in real life, we may need to locate specific data items in a sea of data items. For instance, you might need to know a vehicle’s registration number. What is the fastest way of doing it?
Some search algorithms are meant to help you avoid having to go through all of the data. You should be familiarized with two types of search algorithms: binary search and linear search. They will help you deal with data.
Introduction to binary search
Binary search, also known as ‘divide-and-conquer’, requires that the initial array be sorted before searching.
Binary is the name of this algorithm, which splits the array in two. A binary search will initially look at the item at the center of the array and then compare it with the search terms.
These are three scenarios that could be possible in binary search
Search criteria: middle item: Item found
Search criteria for less than middle items: Search the first half
If your search criteria are more extensive than the middle item, you can search the upper half of this array.
Continue to divide the array until the middle item meets your search criteria.
When is it appropriate to use a binary search?
If there are many items on the list that change frequently, and they are constantly added or removed, the time required to re-order them to permit a binary search may be longer than for a simple serial search.
A binary search can be very efficient if the list is long and static (e.g. a database of telephone number numbers). In math terms, it takes 2log2(n), for a binary look over n items.
An example of how binary search works
Ask a friend for a number between 1 to 100. Let’s call the number x. In the worst case, how many times can we find the answer to x? We can use the questions to determine if x is greater or smaller than a number.
The solution is 7. It is not easy to guess the answer. What logic is behind these problems?
So, here’s how you do it in the fastest way:
Divide the numbers into two halves, which are 1 to 50, then 50 to 100. Technically, the best first guess is 50. By doing that, you can eliminate half of the remaining numbers if you know 50 is higher or lower than the target.
Say, it’s higher than the written one. The second guess should be 25. And again, from the middle one. Then, this continues until you find the identical value you’re looking for.
Analysis of the example: the power of the 2
So, the secret to the best solution lies in number 2. In this case, the number of elements is 100. When you raise 2 with the power of 6, you get 64, while with 7, you got 128. Thus, the answer should be 7.
A linear search might be easier if the list is short.
If the list contains random items, then a linear search will be the best way to search.
A linear search will be more effective if the list is biased so that the most searched items are at the beginning.
An example of linear/serial search
You can also call a linear search a serial search. In this search algorithm, every item is compared to the one we are looking for.
Before the search starts, you will need to enter your search criteria. Then, you will start the search with the first item, and then compare each item until you find the same item.
You can search, for example, the number 1 in this array.
Index: 0 1 2 3 4
Value: 7 5 1 3 6
The search starts at index 0. Then, it compares the index 0 elements to the search criteria. In this case, 1 is the first value you find. Is 2 equal to 1? Of course, not. So, the comparison process goes on with index 2 with the number 1. Is 1 equal to 1? Well, that is the number you want. Then, the algorithm can continue searching for instances up to the end of the array or it can stop searching.
A linear search has many advantages
Linear search ensures fast searches for small to medium datasets. Small to medium arrays can now be searched quickly with today’s powerful computers.
Using linear search doesn’t need you to sort the list in advance. Linear searching is not like a binary search, and it can deal with unsorted arrays.
Insertions and deletions won’t affect the linear search algorithm. As we’ve mentioned, the linear search doesn’t need sorted elements in the array, so adding or deleting elements won’t affect its process. A linear search may be more efficient than other algorithms because it does not require the list to resort after any insertions or deletions.
A linear search has its disadvantages
When it comes to large datasets, linear search can be extremely time-consuming in the worst case. It might have to go through millions of names to find the name you are looking for from a database of names. In this case, however, binary search is much more efficient when names are arranged in alphabetic order.
Evaluation of binary and linear searches
A binary search can be a bit more difficult to program than a linear search, but it is much more efficient.
Example: A 16-element array can be found using a binary search. In the worst case, it will take four attempts to find the element. (2*2*2*2 = 16).
This would apply to an array of 1,000,000 elements. The worst-case scenario would be 20 attempts, while 1,000,000 probes would be the best case for a linear search with 1,000,000 items.
Search algorithms are essential in computer science. When to choose linear search and when should you use binary search? You should probably know now from this article.