Linear Search in Python

Linear Search in Python

Searching is an important operation in programming. It is used to find a particular element from a collection such as a list or array. Python provides different ways to search for values, and Linear Search is one of the simplest searching algorithms to understand.

Linear Search, also called Sequential Search, checks the elements of a list one by one until the required element is found or the complete list has been searched.

In this tutorial, we will learn what Linear Search is, how its algorithm works, how to implement it in Python, its time complexity, and when it should be used.

Complete Advance AI Topics: Click Here
SQL Tutorial: Click Here

Types of Searching

There are two commonly discussed searching techniques:

1. Linear Search
2. Binary Search

Both algorithms can be used to find an element, but their working methods and performance are different. Linear Search checks elements sequentially, while Binary Search repeatedly divides a sorted search space into smaller parts.

What is Linear Search?

Linear Search in Python is a simple searching algorithm that checks every element in a list from the beginning until the required value is found.

Suppose we have the following list:

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

If we want to search for 7, Linear Search starts with 1, then checks 3, 5, 4, and finally finds 7.

When the element is found, its index position can be returned. If the complete list is checked and the element does not exist, the algorithm can return -1.

How Does Linear Search Work?

The basic process of Linear Search is straightforward:

1. Start from the first element of the list.
2. Compare the current element with the value being searched.
3. If both values match, return the element’s index.
4. If they do not match, move the next element.
5. Continue until the element is found or list ends.
6. If the element is not found, return -1.

Linear Search Algorithm

The general structure of the Linear Search algorithm can be written as follows:

LinearSearch(list, key)

    for each item in list:
        if item == key:
            return its index

    return -1

The algorithm compares the search value with each item sequentially. It does not require the list to be sorted.

Linear Search in Python Using a Function

Let’s implement Linear Search using a Python function:

def linear_search(lst, n, key):
    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)

result = linear_search(lst, n, key)

if result == -1:
    print("Element not found")
else:
    print("Element found at index:", result)

Output

Element found at index: 4

Explanation of the Program

Let’s understand the above Python program step by step.

• The linear_search() function accepts the list, its length, and the value to search.
• The for loop visits each list element one by one.
• The condition lst[i] == key compares the current element with the search value.
• When a match is found, the function returns the index.
• If no match is found after checking all elements, the function returns -1.

In this example, 7 is located at index 4 because Python list indexing starts from 0.

Linear Search Without a Function

Linear Search can also be implemented directly using a loop without creating a separate function.

numbers = [10, 20, 30, 40, 50]
key = 30

found = -1

for i in range(len(numbers)):
    if numbers[i] == key:
        found = i
        break

if found == -1:
    print("Element not found")
else:
    print("Element found at index:", found)

Output

Element found at index: 2

Linear Search Using User Input

numbers = [10, 20, 30, 40, 50]

key = int(input("Enter element to search: "))

found = -1

for i in range(len(numbers)):
    if numbers[i] == key:
        found = i
        break

if found == -1:
    print("Element not found")
else:
    print("Element found at index:", found)

This approach makes the program interactive because the user can enter the value that needs to be searched.

Time Complexity of Linear Search

The performance of Linear Search depends on the position of the required element.

Case	Time Complexity	Description
Best Case	O(1)	The element is found at the first position.
Average Case	O(n)	The element is found after checking several elements.
Worst Case	O(n)	The element is at the end or is not present.

The space complexity is generally O(1) when the search is performed directly on an existing list without creating additional data structures.

YT:- DecodeIT

Linear Search vs Binary Search

Feature	Linear Search	Binary Search
Searching Method	Checks elements sequentially	Divides the search space
Data Requirement	Does not require sorted data	Requires sorted data
Best Case	O(1)	O(1)
Worst Case	O(n)	O(log n)
Implementation	Simple	More involved

Advantages of Linear Search

• Easy to understand and implement.
• Works with unsorted lists.
• Does not require additional data structures.
• Useful for small datasets.
• Can be implemented with a simple loop.

Limitations of Linear Search

• It can be slow for large datasets.
• In the worst case, every element must be checked.
• Repeated searches can become inefficient when the dataset is large.

Conclusion

Linear Search in Python is one of the simplest searching algorithms.

Learning Linear Search is useful for understanding basic searching concepts and building a strong foundation in algorithms and data structures.

Frequently Asked Questions

What is Linear Search in Python?

Linear Search is an algorithm that checks each element of a list sequentially until the required element is found or all elements have been checked.

What is the time complexity of Linear Search?

The best-case time complexity is O(1), while the average and worst-case time complexity is O(n).

Does Linear Search require a sorted list?

No. Linear Search can work with both sorted and unsorted lists.

What happens if an element is not found?

In the example implementation, the function returns -1 when the searched element is not present in the list.

What is the difference between Linear Search and Binary Search?

Linear Search checks elements one by one, while Binary Search repeatedly divides a sorted search space to locate the target more efficiently.

Keywords

Linear Search in Python, linear search in python using list, linear search algorithm, linear search in Python example, linear search in Python user input, linear search in Python without function, linear search using recursion in Python, binary search in Python, Python searching algorithms, sequential search in Python, linear search program in Python, linear search example, Python list search, linear search vs binary search, data structures in Python Linear Search in Python