Software Development Python

How to perform Linear Search in Python?

How to perform Linear Search in Python?

Introduction

In this article, we will learn about linear search in Python. Searching is a technique for determining whether or not a specific element exists in a given list.

There are two types of searching

  1. Linear Search
  2. Binary Search

Both techniques are commonly used to find an element in a given list.

Linear search, or sequential search, is a technique for locating elements within a list. It compares each element to the value that we are looking for. If both match, the element is found, and the algorithm returns the index position of the key.

CONCEPT OF LINEAR SEARCH

  • Let's go over the steps to find the element key = 7 in the given list.

Step 1: Begin the search with the first element and check key = 7 for each element of list x.


STEP -2: If an element is found, return the key's index position.


STEP -3: If the element can’t be found, the return element is not found.       Here, luckily, we found element 7.


ALGORITHM

Linear Search :

  1. Start from the leftmost element of the list and one by one compare the "key" with each element of the list.
  2. if "key" matches with an element, return True.
  3. else return False.  

* ‘key’ = element that needs to be searched

CODE AND OUTPUT

def linear_Search(list1, n, key):  

  

    # Searching list1 sequentially  

    for i in range(0, n):  

        if (list1[i] == key):  

            return i  

    return -1  

  

  

list1 = [1 ,3, 5, 4, 7, 9]  

key = 7  

  

n = len(list1)  

res = linear_Search(list1, n, key)  

if(res == -1):  

    print("Element not found")  

else:  

    print("Element found at index: ", res)  

write your code here: Coding Playground

CLARIFICATION

In the preceding code, we defined the function linear Search(), which takes three arguments: list1, the length of the list, and the number to search. We defined a for loop that iterates through each element and compares it to the key value. If the element is found, return the index; otherwise, return -1, indicating that the element does not exist in the list.

LINEAR SEARCH COMPLEXITY

*The time complexity for the best case is O(1)

RECURSIVE APPROACH

# This is similar to the above one, with the only difference

# being that it is using the recursive approach instead of iterative.



def search(arr, curr_index, key):

if curr_index == -1:

return -1

if arr[curr_index] == key:

return curr_index

return search(arr, curr_index-1, key)

write your code here: Coding Playground

Time and Space Complexity = O(n).

SUMMARY

As it checks each element to obtain the desired number, the linear search algorithm is best suited for smaller lists (100). If there are 5000 elements If the desired element is at the last position in a list, comparing each element in the list will take a long time. We can use the binary search algorithm to get a quick result.

In this article, We've covered the fundamentals of linear search.