Python Program to implement linear search algorithm in array

In this simple python program, we need to search an element in an array in python.

To understand this example, you should have knowledge of the following Python programming topics:

This python program is to understand how linear search is performed simply using a for loop and if condition.

What is Linear Search?

Linear search is the basic method used for searching an element in an array, list, or any other data structure. It is also called Sequential search because the element is searched sequentially in a list. There will be an array of elements and one element to search whether it belongs to the given set of elements. As the name indicates Linear search compares search element with the elements of the array one by one from the starting index to last. If a match is found it will output the index of array element where it got the match otherwise it gives an output ' item not found in the set '. 

Unlike Binary search, Linear search is widely used to search an element in an unordered list i.e., the list containing elements that are not sorted.  Although it is suitable for a smaller list (<100). Suppose there is a 10,000 element list and search element is available at the last position, sequential search will consume much time by comparing with each element of the list. Thus the worst-case time complexity of the linear search algorithm is O(n).


How to implement Linear Search in Python?

  • First, we have to traverse the array elements using a for loop.
  • In each iteration of for loop, compare the search element with the current array element, and -
  • If the element matches, then save the index of the corresponding array element and set a search flag with value 1 also break the loop.
  • If the element does not match, then move to the next element until the end of the array.
  • Now, check whether the search flag is set or not. Yes, means we got a match in the array otherwise there is no match or the search element is not present in the given array.

Consider an example,

Here we are taking an array [6, 2, 5, 7, 9] and we need to search whether the number 5 is present in the array or not. Now iterate the array using a for loop from starting index to last, and check. Whether array element is equal to search element 5. If got a match then save the index for printing the result otherwise print the message “element not found”.

ALGORITHM

STEP 1: Initialize the array arr with some predefined values.

STEP 2: Define variable item with the search value and flag with a zero

STEP 3: Start a for loop from zero to the length of the array for comparing each element in the array.

STEP 4: Use an if condition to check whether the element is equal to the search element, and

STEP 5: If the condition is true then save the current array index and change the flag to 1, flag value 1 means we got our search element in array, so break the for loop

STEP 6: otherwise for loop will go for the next iteration until the end of the array.

STEP 7: Check the flag value and print the result accordingly.
 

Python Source Code

                                          arr = [6, 2, 5, 7, 9]
item = 5
n = len(arr)
flag=0
for i in range(0, n):           # traverse the array
        if (arr[i] == item):    # check whether array element and search element is same
            result= i;          # save index of the matching element
            flag=1;             # set flag to indicate we got a match
            break;

if(flag == 0):
    print("Element not found")
else:
    print("Element found at index: ", result)
                                      

OUTPUT

Element found at index:  2