{"id":11772,"date":"2023-01-17T09:49:52","date_gmt":"2023-01-17T09:49:52","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=11772"},"modified":"2023-04-25T09:18:31","modified_gmt":"2023-04-25T09:18:31","slug":"linear-search-in-data-structure","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/linear-search-in-data-structure\/","title":{"rendered":"Linear Search in Data Structure"},"content":{"rendered":"

\"\"<\/p>\n

Linear search is a basic searching algorithm used in computer programming to find a specific element in a collection of data. It involves iterating through each element in the collection one by one until the target element is found. This algorithm is simple and easy to implement.<\/p>\n

One of the most widely applied programming techniques in daily life is searching. It’s everywhere, whether you’re browsing on Google, shopping on Amazon, or discovering the next Netflix series to binge. If you stop to think about it, you probably found this article by searching on Google or possibly Bing alone today.<\/p>\n

Definition of Search in Computer Programming<\/h2>\n

In computer programming, the process of finding a particular item within a data structure is commonly known as search. This is often necessary when trying to extract useful information from a dataset.<\/p>\n

For Example,<\/strong>
\nLet\u2019s take the following example where we want to search for the word "PrepBytes" in the sentence:<\/p>\n

\u201cLearn coding from PrepBytes\u201d<\/code><\/pre>\n
PrepBytes is the fourth word in the previous statement, as can be seen. When the data set is so little and you are using your naked sight to search, that is simple.<\/p>\n
It won\u2019t be so simple, though, if someone asks you to locate a word in a text that has tens of thousands of words and sentences.<\/p>\n
That\u2019s exactly what we\u2019ll study today: how to write a program to find an element in a data set.<\/p>\n
Linear Search In Data Structure<\/h2>\n
Let’s imagine that we are attempting to find the value K within an array of random integers.<\/p>\n
Suppose the array is 5 3 12 9 45 1 22
\nK = 9 is the value of the element we’re looking for.<\/p>\n
What is the most logical approach to take?<\/strong>
\nYou’ve just defined Linear Search yourself if you’re planning to start at the beginning of the array and see if each element is equal to K or not until you either find K or reach the end.<\/p>\n
Let’s give it a clearer definition.<\/p>\n
In a linear search, we go over each element of the array one at a time and see if it matches the element we’re looking for. Because it examines each element in turn, it is also known as a sequential search.<\/p>\n
The linear search involves scanning an array or list sequentially until the desired element is found. If the value K is found during this process, it means that K is present in the array. Conversely, if K is not found after scanning through the entire array, it can be inferred that K is not in the array. Let\u2019s try using linear search for the input mentioned above.<\/p>\n
5 3 12 9 45 1 22 \u2013 Found K = 9 at index 3<\/p>\n
Working of Linear Search In Data Structure Algorithm<\/h2>\n
As you can see, in the fourth comparison, we found K.<\/p>\n
You could counter that there is no need to begin at the beginning rather than the middle or the end. We can carry out either of those, you’re right. But consider this: Does it truly assist? No, really, is the response.<\/p>\n
Only the fourth iteration contains the number 9 if you attempt to search for it from the end rather than the beginning.<\/p>\n
5 3 12 9 45 1 22 \u2013 Found K = 9 at index 3<\/p>\n
What is Linear Search In Data Structure Algorithm?<\/h2>\n
If K is present in the first half of the array, it will be simpler to start at the beginning if K is present. On the other hand, it is preferable to begin at the end if it appears in the second part.<\/p>\n
But stop and think about it\u2014do we really know where the element might be in a wholly random array? Or maybe just the fact that it exists or not? Right, we don’t. We use linear search for that purpose.<\/p>\n
In fact, it is very possible that K will be the first element of the array if you start at the end and the last if you start from the first.<\/p>\n
As a result, if we assume the worst, we will always end up searching the entire array. Therefore, it doesn’t really matter where we begin the search.<\/p>\n
Algorithm For Linear Search In Data Structure<\/h2>\n
The algorithm for Linear Search in Data Structure is given below in a stepwise manner.<\/p>\n
    \n
  1. Initialize i = 0 and n = size of array<\/li>\n
  2. If i >= n, which means we have reached the end of the array and we could not find K. We return -1 to signify that the element K was not found.<\/li>\n
  3. If arr [ i ] == K, it means that we have found an element that is equal to K at index ‘i\u2019 and we do not need to search the remaining array.We immediately return the value i from here, which is the index in this array at which K was located.<\/li>\n
  4. If arr [i]!= K, the current element of the array will not equal K, and we will repeat step 2 with the subsequent element by incrementing i i.e. ++i.<\/li>\n<\/ol>\n
    Dry Run For Linear Search In Data Structure<\/h3>\n
    The dry run for linear search in data structure is given below for a better understanding of the topic.<\/p>\n
    \"\"<\/p>\n
    Implementation of Linear Search in Data Structure<\/h3>\n
    Below is a simple code implementation of Linear Search in Data Structure.<\/p>\n\t\t\t\t\t\t