Python Program for Linear Search with Example and Explanation

A Python program for linear search checks each element in a list one by one using a for loop and if condition to find the target value; for example, for i in range(len(arr)): if arr[i] == target: return i.

Examples

Inputarr = [5, 3, 7, 1, 9], target = 7

Output2

Inputarr = [10, 20, 30, 40], target = 25

Output-1

Inputarr = [], target = 5

Output-1

How to Think About It

To do a linear search, start from the first item in the list and check if it matches the target. If it does, stop and return the position. If not, move to the next item and repeat until you find the target or reach the end of the list.

Algorithm

1

Get the list and the target value.

2

Start from the first element in the list.

3

Compare the current element with the target.

4

If they match, return the current index.

5

If not, move to the next element.

6

If the end of the list is reached without a match, return -1.

Code

python

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# Example usage
arr = [5, 3, 7, 1, 9]
target = 7
result = linear_search(arr, target)
print(result)

Output

2

Dry Run

Let's trace the example where arr = [5, 3, 7, 1, 9] and target = 7 through the code.

1

Start loop at index 0

Check if arr[0] (5) == 7 → No

2

Move to index 1

Check if arr[1] (3) == 7 → No

3

Move to index 2

Check if arr[2] (7) == 7 → Yes, return 2

Index	Value	Target	Match?
0	5	7	No
1	3	7	No
2	7	7	Yes

Why This Works

Step 1: Loop through each element

The for loop goes through each item in the list one by one to check for the target.

Step 2: Compare current element with target

The if statement compares the current element to the target value to find a match.

Step 3: Return index if found

If a match is found, the function returns the current index immediately to stop searching.

Step 4: Return -1 if not found

If the loop finishes without finding the target, the function returns -1 to indicate absence.

Alternative Approaches

Using while loop

python

def linear_search_while(arr, target):
    i = 0
    while i < len(arr):
        if arr[i] == target:
            return i
        i += 1
    return -1

print(linear_search_while([5,3,7,1,9],7))

This uses a <code>while</code> loop instead of <code>for</code>, which is slightly longer but works the same.

Using Python's index() with try-except

python

def linear_search_try(arr, target):
    try:
        return arr.index(target)
    except ValueError:
        return -1

print(linear_search_try([5,3,7,1,9],7))

This uses Python's built-in <code>index()</code> method with error handling, which is simpler but less explicit.

Complexity: O(n) time, O(1) space

Time Complexity

The search checks each element once, so time grows linearly with list size, making it O(n).

Space Complexity

No extra space is used besides variables, so space complexity is O(1).

Which Approach is Fastest?

All linear search methods have similar speed; using built-in index() is concise but may raise exceptions.

Approach	Time	Space	Best For
For loop linear search	O(n)	O(1)	Clear step-by-step search
While loop linear search	O(n)	O(1)	Alternative loop style
Built-in index() with try-except	O(n)	O(1)	Concise code, handles errors