What Is Linear Search Algorithm and Why Data Scientists Should Know About It? 

From netizens to Data scientists, to finding a particular book from a bookshelf, or finding the right credit card to use or to surf the internet, we all have struggled. Performing the task of searching is a common task in our daily lives. 

In computer science, searching is a very common exercise. It refers to finding a particular location of an element or a particular goal state in a Data Structure. It can be linked lists, arrays, search trees, or even hash tables. In machine learning, it refers to finding the maxima minima or the desired goal state.

An uninformed search problem is where nothing is informed about the state of the search problem or, such as closeness, the location of the goal. The first thing one needs to find out is the complexity of the linear search method or brute force method. Then one can use more optimized uninformed search algorithms like Binary search, BFS, DFS, etc., to have better results.

A linear search may not give us the best solution for the search problem, but it gives us the baseline to optimize our algorithm to achieve the best optimal solution. Every advanced programming concept and algorithm builds up upon the knowledge of the basic Data Structure and Algorithms. The Linear search algorithm is the first basic search algorithm taught in every Computer science degree or Data Science degree in India. 

Now let us start our discussion on the Linear Search algorithm. For the sake of easier understanding, we will limit our discussion to Linear Search in arrays. 

 

What is a Search Algorithm? 

The search algorithm can be defined as an algorithm that resolves a search problem. It retrieves the information stored in a data structure or calculates the search space in a problem domain.  

The searching algorithm is meant to find a specified value or a value satisfying specified constraints from a given data structure. It can be a  tree, an array, or a linked list, or any other type of data structure, 

The Algorithm search for a target (key) in the search space, like-

  1. All students in a computer science course
  2. Many platforms in India offer the best data science certification online
  3. Statistics scores of all students in a class

The result of a search operation can be of two types, i.e. 1. Success  2. Failure, If the specified value is found on the Data Structure, it results in Success, and if it fails to find so, it fails. 

The search algorithms can be classified into 2 types based on the search operations, and they are- 

  1. Sequential Search: When data items are present in the collection, such as a list or an array, there is relativity present, and the index number of that list is ordered. Hence, the data values can be visited in a sequential manner using index numbers.
  2. Interval Search: Interval search is mainly used where the data structure is in a sorted manner.  Interval search methods are more efficient than sequential search as they repeatedly target the center of the search structure and divide the search space in 2 half. For Example, Binary Search.

 

Linear Search

A linear search or sequential search is an algorithm to find a given value within a list. It checks every element of the list one by one until it finds a match or the whole list has been searched. 

In many cases, linear search is not a practical choice. Other search algorithms like Binary search, Hash table are more feasible ones.

Procedure LinearSearch( x:  integer  : distinct integer)

1: i := 1

2:  while i ≤ n and x !=  do

3:        i := i 1

4:  end while

5:   if I ≤ n, then

6:       location:= i

7:   else

8:        location := 0

9:   end if

10:  return location {location is the subscript of the term that equals x, or is 0 if x is not found}

Flow-Chart

Example:

Consider the given array of No. We are to find the value a=1, 

In linear search, the algorithm will start with the first element of the array and then will compare it with the given value a=1. If the match isn’t found, it will jump to the next element of the array and compare it with the given value.

 

 If the element is found, it will return the index of that element. If not, then the process will repeat until it finds a match or the whole list searched.

 

If no index is returned even after the whole list is searched, the value isn’t present. 

Linear Search Code in Python 

def Linear_Search(arr, n, key):

    for loc in range(n):

        if arr[loc] == key:

            return loc

    return -1

 

arr = [“Tony”, “Anton”, “Barry”, “Michael”, “James”]

Linear_Search(arr, 5, “Tony”) #return 0

Linear_Search(arr, 5, “Barry”) #return 2

Linear_Search(arr, 5, “Tim”) #return -1

 

Time Complexity of Linear Search

The time complexity of the linear search algorithm is O(n) for n numbers of elements in the lists. 

Best case-

 In the best possible scenario,

  • The searched element is present at the first position of the list.
  • In this case, the search will return the solution with just one comparison.
  • Hence for the best-case scenario, the complexity would be O(1).

Worst Case-

 

In the worst-case scenario,

  • The element is present at the last position of the list or may not be present at all.
  • In the first case, the search will result in success after n comparison.
  • In the second case, the search terminates in failure with n comparisons.
  • Thus in the worst-case scenario, the linear search will have O(n) time complexity.

Thus, we have-

 

                                                                    The Time Complexity of the Linear Search Algorithm is O(n).

                                                                          Here, n is the number of elements in the linear array.

Application:

Linear search is a very simple algorithm to implement. It is more practical to use linear search when we have only a few elements or find a specified value in an unordered list. 

When many values have to be searched in the same list, it is often worthwhile to pre-process the list before using a faster method.   For example, one may sort the data structure to employ Binary search to find the solution of the search problem. 

But in real life, even though in theory there are search algorithms that are faster than linear search(Binary Search), in practice on medium-sized arrays (around 100 items or less), it might not be worth the trouble of sorting the data structure to use the Binary search algorithm. It only makes sense to sort the data if it is large enough because the initial time to sort the data is comparable to many linear searches.

 

Conclusion:

As a Data Scientist, one will have many search algorithms in his arsenal which are fast and give the best result. But for a given problem, one has to start with the baseline solution available for that problem. Linear search or brute force method provides the starting point to find a solution to the search problem. 

 

Nowadays, there are many institutions or online platforms in India which offer the best Data science course in India or Certification course on Data Science and Programming. One enrolling in those courses should always focus on building the basic concept of each subject.

Only knowing the popular algorithms and key topics which are trending is not going to help one build a solid foundation of the subject.   So always get your foundation solid when you start your learning journey in the field of Data Science. 

 

Leave a Comment