Linear Search

Introduction

Let’s suppose we have an array arr= [4,6,3,7,8,5,34,26,23] of length n and we want to find the index for 5 in this array, then the most intuitive way to search is that we compare each element of the array with 5 and if it matches we return the index of 5, this method of traversing the array for searching an element is called linear search or sequential search.

Let’s take another example

arr = [9,29,46,23,75,98] 
# find an index of 75
# desired output 4

for finding the index of 75 these are the steps you must follow

• iterate from 0 to len(arr)-1 and compare each element of the arr
• if there is a match then return the index of the arr and if the element is not in the array return -1

Python implementation

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

# driver code
arr =  [9,29,46,23,75,98]
x = 75
result = linearSearch(arr,x)
print("Elemen is present at Index ",result)

in the above code, we are defining a function linearSearch and it takes two arguments an array and an element to search, after that we are running a for loop with a range function with a length of the arr i.e 6, so in the worst case, if the element is present in the array, we will iterate 6 times. after that in the if block, we are checking if the element at the ith index is equal to the element we want to search and if that’s the condition then we return the index of the element.

for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1

# first iteration
if arr[0] == x: -> i.e 9 == 5 -> False
# second iteration
if arr[1] == x: -> i.e 29 == 5 -> False
# third iteration
if arr[2] == x: -> i.e 46 == 5 -> False
# fourth iteration
if arr[3] == x: -> i.e 23 == 5 -> False
#fifth iteration
if arr[4] == x: -> i.e 75 == 5 -> True
#our loop will stop here and it will return index 4

JavaScript implementation

function linearSearch(arr, x) {
    for (let index = 0; index < arr.length; index++) {
        if (arr[index] === x) {
            return index;
        }
    }
    return -1;
}

// driver code
arr =[9,29,46,23,75,98];
x =  75;
result = linearSearch(arr, x);
console.log(result);

Note

If the same element is present more than one time then the linear search will return the index of the first element.

arr = [9,29,46,23,75,75,75,98] 
# here 75 is present at multiple index i.e index 4,5,6
# so the linear search will return index of only first element i.e 4

Time Complexity

The worst case of the algorithm occurs when we search through the whole array and an element is not present in the array in that case algorithm will do f(n) = n + 1 comparisons, thus in the worst case, the running time complexity of our algorithm depends on n i.e length of the array. time complexity O(n)