Linear search/ sequential search

Linear search is the easiest algorithm to search an item in an array/ list.
It is The most common algorithm to search an element in an unsorted array/ list. 
However, it is not effective for sorted arrays.

Linear search compares every single element in the array (starting from 0 till the end of the array) with the given element. 
If given element = array[index ], then return this index.
If all elements in the array have been compared with the given element and the given element could not be found in the array, then return -1.

Time complixity :

Worst Case:         O(N)
Average Case:    O(N)
Best Case:             O(1)  When the given element is found at the first index of the array.

📢Recommended: Please try to implement  the algorithm on your own first, before looking at the code down below.

______________________________________________

🎁code:

"""

AUTHOR: Khaled Badran

DATE:   05/09/2020

"""

def linear_search(unsorted_arr, x):

    # x is the element we are searching for.

    for i in range(len(unsorted_arr)):

        if unsorted_arr[i] == x: 

            return i

    return -1        

def optimized_linear_search(sorted_arr, x):

    for i in range(len(sorted_arr)):

        if sorted_arr[i] == x:

            return i

        elif sorted_arr[i] > x:

            break

    return -1        

unsorted_arr = [1, 2, 100, 5, 12, 63, 78, 37, 53, 54, 82, 102]

print("Linear search:")

print("unsorted_arr = " + str(unsorted_arr))

print("Index of 100 in the unsorted_arr = " + str(linear_search(unsorted_arr,100)))

print("Index of 102 in the unsorted_arr = " + str(linear_search(unsorted_arr, 102)))

print("Index of 51 in the unsorted_arr  = " + str(linear_search(unsorted_arr, 51)))

print("")

sorted_arr = [1, 2, 5, 12, 37, 53, 54, 63, 78, 82, 100, 102]

print("optimized linear search for sorted arrays:")

print("sorted_arr = " + str(sorted_arr))

print("Index of 0 in the sorted_arr   = " + str(optimized_linear_search(sorted_arr, 0)))

print("Index of 51 in the sorted_arr  = " + str(optimized_linear_search(sorted_arr, 51)))

print("Index of 100 in the sorted_arr = " + str(optimized_linear_search(sorted_arr,100)))

print("Index of 102 in the sorted_arr = " + str(optimized_linear_search(sorted_arr, 102)))

______________________________________________

output:

unsorted_arr = [1, 2, 100, 5, 12, 63, 78, 37, 53, 54, 82, 102]
Index of 100 in the unsorted_arr  = 2
Index of 102 in the unsorted_arr  = 11
Index of 51 in the unsorted_arr     = -1

optimized linear search for sorted arrays:
sorted_arr = [1, 2, 5, 12, 37, 53, 54, 63, 78, 82, 100, 102]
Index of 0 in the sorted_arr       = -1
Index of 51 in the sorted_arr    = -1
Index of 100 in the sorted_arr = 10
Index of 102 in the sorted_arr = 11

______________________________________________