Python Program for Linear Search

What is linear search ?

Linear search is used on a collection of elements like array. Linear search technique is traversing a list of elements from starting index to ending index till that are found on the way.

Example, consider collection of elements as below
collection sorted

Linear search: searching starts from index 0 to ending index.

Linear Search Time complexity

Linear search time complexity is O(N), here each element in an array is compared only once and N is the number of elements in the collection.

Linear Search Python Program using enumerate method

#!/usr/bin/python                                                               
                                                                                
def linear_search(search_key, list_vals):                                       
    for index, val in enumerate(list_vals):                                     
        if search_key == val:                                                   
            return index;                                                       
    return -1;                                                                  
                                                                                
                                                                                
if __name__ == "__main__":                                                      
    list_vals = [10, 20, 30, 40, 50, 60, 70, 80];                               
    key = int(raw_input("Please enter a string:"));                             
    print("key is found at index: %d" % linear_search(key, list_vals));

Output:

$ python linear-search.py
Please enter a string:10
key is found at index: 0
$ python linear-search.py
Please enter a string:30
key is found at index: 2
$ python linear-search.py
Please enter a string:50
key is found at index: 4
$ python linear-search.py
Please enter a string:9
key is found at index: -1

Linear Search Python Program using range method

#!/usr/bin/python                                                               
                                                                                
def linear_search(search_key, list_vals):                                       
    for index in range(0, len(list_vals)):                                      
        if search_key == list_vals[index]:                                      
            return index;                                                       
    return -1;                                                                  
                                                                                
                                                                                
if __name__ == "__main__":                                                      
    list_vals = [10, 20, 30, 40, 50, 60, 70, 80];                               
    key = int(raw_input("Please enter a string:"));                             
    print("key is found at index: %d" % linear_search(key, list_vals));

Output:

$ python linear-search.py
Please enter a string:20
key is found at index: 1
$ python linear-search.py
Please enter a string:30
key is found at index: 2
$ python linear-search.py
Please enter a string:3
key is found at index: -1

« Previous Next »

Python Programming Language Examples