Linear Search in Python

Linear Search in Python

Python is one of the most powerful and user-friendly programming languages. It allows developers to write concise and efficient code, making it a preferred choice among programmers. In this tutorial, we will explore the concept of Linear Search in Python. One essential method for figuring out whether a specific element is in a list is searching.

Types of Searching

There are two main categories of search methods:

1. Linear Search
2. Binary Search

Both techniques are widely used to search for an element in a list, but their efficiency varies depending on the dataset size.

What is Linear Search?

The most basic search algorithm is linear search, sometimes referred to as sequential search. Until the requested element is located or the list’s end is reached, it checks each element in the list one at a time.

The algorithm compares each element with the key (the value we are searching for).The element’s index is returned if a match is discovered. Otherwise, it returns a message indicating that the element is not present in the list.

Complete Python Course with Advance topics:-Click here

Concept of Linear Search

Let’s go through the steps involved in performing a Linear Search for a given key (e.g., 7) in a list:

1. Compare it with the key (7) after beginning the search with the first element.

2. Return the index point if a match is discovered.

3. Return a message indicating that the element is absent if, after verifying every element, no match is discovered.

Linear Search Algorithm

The structure of the Linear Search Algorithm is as follows, given a list of n elements and a key to be searched:

LinearSearch(list, key)
  for each item in the list:
    if item == key:
      return its index position
  return -1

Python Implementation of Linear Search

Let’s use Python to implement the Linear Search algorithm.

def linear_search(lst, n, key):  
    # Searching the list sequentially  
    for i in range(0, n):  
        if lst[i] == key:  
            return i  
    return -1  
  
# Sample list
lst = [1, 3, 5, 4, 7, 9]  
key = 7  
  
n = len(lst)  
res = linear_search(lst, n, key)  
if res == -1:  
    print("Element not found")  
else:  
    print("Element found at index:", res)  

Output:

Element found at index: 4

Explanation:

• We define a function linear_search(), which takes three arguments: lst (the list), n (length of the list), and key (the element to search).
• A for loop iterates through the list, comparing each element with key.
• If a match is found, the function returns the index.
• If the loop completes without finding the element, it returns -1, indicating that the element is not present.

Time Complexity of Linear Search

TThe effectiveness of the Linear Search algorithm is assessed under many conditions:

• Best Case: O(1)- The first position is where the element is found.
• Average Case: O(n) – When the element is somewhere in the middle.
• Worst Case: O(n)- When an element is absent from the list or at the end of the list.

When to Use Linear Search?

Linear Search is suitable for small datasets (e.g., fewer than 100 elements) because it scans each element individually. However, for larger datasets, it becomes inefficient. For example, if a list contains 10,000 elements and the desired element is at the last position, the algorithm will take a long time to complete.

Download New Real Time Projects :-Click here
Complete Advance AI topics:- CLICK HERE

Alternative: Binary Search

To achieve faster results for large datasets, Binary Search is a better alternative. It uses a divide-and-conquer approach, significantly reducing search time. We will explore Binary Search in the next tutorial.

Stay tuned for more programming tutorials at UpdateGadh, where we simplify complex concepts for developers of all levels!

linear search in python using list
binary search
linear search in python user input
linear search in python without function
linear search in python w3schools
linear search in python class 12
linear search algorithm
linear search in python using recursion
binary search in python
python compiler
linear search in python with example