Short Notes #2: The Linear Search
There has been endless research on searching and sorting algorithms to make the program more efficient and fast. Searching and Sorting algorithms are very vast topics, and it’ll be impractical trying to cover them in one article, and that too when the article is named “Short Notes”, it’ll be against the purpose. So I’ll be writing various short notes on various algorithms.
But, what’s the need for so many algorithms?
Needless to say, one can find the need for searching an element in the given collection of data in many apps that are running in production right now in the market.
- Whatsapp?
Yes, we use search contacts in the contacts list, we search for media, and messages as well! - Facebook? LinkedIn? Instagram? Twitter?
Of course! we search for different pages and profiles. - A simple dictionary app?
Yes, again we lookup for words for their meanings. - Medium app?
Yes, we search for different articles - Google?
Of course, it is a search engine.
Almost all the apps that we use, in some way or the other need to search data in a given pool of data.
Generally, competitive coders learn many searching and sorting algorithms to make their code more efficient, but even if you are a developer and not into competitive programming, still you can’t remain untouched by the need of using searching and sorting algorithms. As I already listed some apps that we use daily need to search data, and as a developer, you will probably need to create such apps where data has to be searched from a given pool of data. I agree that most of the times we use database lookups and predefined functions, but still, as a good coder, you must know what’s happening behind the scenes.
Therefore, for the next few articles, our short notes series will focus on searching and sorting algorithms.
The Linear Search
Also referred to as the sequential search, this is the most simple algorithm to search any given element in a given set of elements. The idea is to look at each and every element in the array and check it’s value
Algorithm
- Make a function that accepts an array and a value as arguments. (The given value has to be searched in the given array)
- Iterate over the array and check if the current element is equal to the given value
- If it is equal, return the current index, otherwise continue
- If the element is not found till the end of the loop, return
-1
Here’s an example of Linear Search in action:
Runtime Complexity
- Best Case Complexity —
O(1) - Worst Case Complexity —
O(n) - Average Case Complexity —
O(n)
Applications
Being the easiest and simplest to implement searching algorithm, it is highly practical to use it when the given data set is small.
Even though there are algorithms which give better runtimes, but still linear search can be used in medium-sized arrays as well.
When many values have to be searched in the same list, it often pays to pre-process the list in order to use a faster method. For example, one may sort the list and use binary search, or build an efficient search data structure from it. Should the content of the list change frequently, repeated re-organization may be more trouble than it is worth.
As a result, even though in theory other search algorithms may be faster than linear search (for instance binary search), in practice even on medium-sized arrays (around 100 items or less) it might be infeasible to use anything else. On larger arrays, it only makes sense to use other, faster search methods if the data is large enough, because the initial time to prepare (sort) the data is comparable to many linear searches
(Source: Wikipedia)
Come, be a part of our community, let’s grow together!
About a month ago I started an initiative named “Daily Codes” where I share one coding question daily, which is solvable in less than half an hour, and the total duration of this challenge is going to be 60 days. This initiative is purely to promote the enthusiasm towards coding in youth, and so that coding becomes a daily habit and people start enjoying solving problems.
Along with the initiative, I formed communities on different platforms to help coders, here are the links in case you wish to be a part.
Whatsapp: http://codetoexpress.tech/joindc/
Slack: https://codetoexpress.tech/invite/
Telegram: https://t.me/codetoexpress
Hope you found the article helpful 😁
Feel free to reach out to me anytime if you want to discuss something :D
I would be more than happy if you send your feedbacks, suggestions or ask queries. Moreover, I love to make new friends and we can be friends, just drop me a mail.
Thanks a lot for reading till end. You can contact me in case if you need any assistance:
Email: theleanprogrammer@gmail.com
Web: http://madhavbahl.tech/
Github: https://github.com/MadhavBahlMD
LinkedIn: https://www.linkedin.com/in/madhavbahl/
