Linear Search in Python

Python ranks among the most widely used and robust programming languages. Its ability to accomplish tasks with minimal code lines enhances its user-friendliness. In this tutorial, we will explore the concept of linear search in Python. Searching refers to the method used to determine whether a specific element exists within a provided list.

Searching can be classified into two main categories -

• ✅ Linear Search
• ✅ Binary Search

Both methods are commonly employed to locate an element within the specified list.

What is a Linear Search?

Linear search refers to a technique for locating elements within a list. This approach is also known as a sequential search. It is regarded as the most straightforward searching algorithm, as it seeks the target element in a sequential fashion.

It evaluates each individual element against the value we are looking for. When a match is identified, the element is located, and the algorithm returns the index position of the key.

Concept of Linear Search

We will examine the subsequent steps necessary to locate the element key = 7 within the specified list.

Step - 1: Initiate the search by examining the first element and compare key = 7 with each item in the list x.

Step - 2: If the element is located, return the index position of the key.

Step - 3: If the element cannot be located, return that the element is not present.

Linear Search Algorithm

A collection of n elements exists along with a key value that needs to be located.

Below is the linear search algorithm.

LinearSearch(list, key)

  for each item in the list

    if item == value

      return its index position

   return -1

Python Example for Linear Search

Let us examine the subsequent Python code that demonstrates the linear search algorithm.

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)

Output:

Element found at index:  4

Explanation:

In the code presented above, a function named linear_Search has been developed, which accepts three parameters - list1, the length of the list, and the target number to find. We established a for loop to traverse each item and compare it against the key value. If the element is located, the function returns its index; if not, it returns -1, indicating that the element is absent from the list.

Linear Search Complexity

Time complexity of linear search algorithm -

• ✅ Base Case - O(1)
• ✅ Average Case - O(n)
• ✅ Worst Case -O(n)

The linear search algorithm is effective for smaller lists (fewer than 100 elements) since it examines each item to find the target value. For instance, if there is a list containing 10,000 elements and the sought-after element is located at the end, the process will be time-consuming as it requires a comparison with every single element in the list.

For obtaining quick results, the binary search algorithm can be utilized.

We have covered the fundamental idea of linear search. In the upcoming tutorial, we will explore the second and most widely used searching algorithm known as Binary search.