Linear Search Algorithm in Array

Linear Search Algorithm

Linear Search Algorithm in Array is part of Learning Data Structure Series. In the previous article of Insert and Delete Operation on Array we learnt to insert and delete element from array.

In this article we will learn to perform search operation to locate an element using Linear Search Algorithm in Array.

Searching Element in Array:
The term searching refers to the process of finding location of an element. There are two methods to search an element in an array:
1. Linear Search
2. Binary Search

Linear search, as the name implies, locates the element in an array linearly whereas binary search finds the element using divide-n-conquer method.

Searching Element Using Linear Search Algorithm in Array

Suppose DATA is a linear array and we want to search ITEM in DATA.

The general process is to compare each element of array DATA with the ITEM. That is, first we test whether DATA[1]=ITEM; if not we test whether DATA[2]=ITEM and so on. If the match is found, we will store the location LOC of the element.

The Linear Search Algorithm in Array is as follows:

LINEAR (DATA, N, ITEM, LOC)

```1. Set LOC:= 0
2. Repeat the step 3 for I:= 1 to N
3.      If DATA[I]= ITEM
Set LOC:= I
[End If]
I:= I+1
[End of Loop]
4. If LOC= 0
Else:
Write: Element is found at location LOC.
5. Exit.
```

Example 1:

 Index 1 2 3 4 5 Value 15 77 50 25 45

Suppose in above array, we want to find whether the element 50 is present or not. Then Linear Search Algorithm will work as follows

Set LOC=0

Check whether DATA[1]=50

 Index 1 2 3 4 5 Value 15 77 50 25 45

If no then continue to next element

Check whether DATA[2]=50

 Index 1 2 3 4 5 Value 15 77 50 25 45

If no then continue to next element

Check whether DATA[3]=50

 Index 1 2 3 4 5 Value 15 77 50 25 45

Yes, we got the element at location 3.

Set LOC = 3

As we found the element at location 3, we set the value of LOC as 3.

There might be the case where element cant be located in an array. If the element is not found in array then we keep the value of LOC as it is (that is LOC=0). Following example of Linear Search Algorithm in Array explains the phenomenon.

Example 2:

 Index 1 2 3 4 5 Value 15 77 50 25 45

Suppose in above array, we want to find whether the element 79 is present or not.

Linear Search Algorithm in Array will work as follows

Set LOC = 0

Check whether DATA [1]= 79

 Index 1 2 3 4 5 Value 15 77 50 25 45

If no then continue to next element

Check whether DATA [2] = 79

 Index 1 2 3 4 5 Value 15 77 50 25 45

If no then continue to next element

Check whether DATA [3] = 79

 Index 1 2 3 4 5 Value 15 77 50 25 45

If no then continue to next element

Check whether DATA [4] = 79

 Index 1 2 3 4 5 Value 15 77 50 25 45

If no then continue to next element

Check whether DATA [ 5]=79

 Index 1 2 3 4 5 Value 15 77 50 25 45

We reach to the end of array. At this stage we have no more elements to check, so control will exit the loop and check whether LOC =0. As the value of LOC is not changed, it is still 0. It means that the element is not present in the array.

In this way we can search an element using Linear Search Algorithm in array.

Drawback of Linear Search Algorithm in Array

Suppose we have 10000 elements in an array and we want to search an element which is at location 9578 then we have to compare 9577 element to reach up to required one. As the number of comparisons increases, the efficiency of Linear Search Algorithm in Array decreases.

This calls for an algorithm which is also efficient in above worst case. Binary Search algorithm stands as a solution for this.

Next article in Learning Data Structure series continues with search operation where we will learn Binary Search Algorithm in Array to find the location of an element with more efficient technique.