Tutorials

# Linear Search

Searching operation in data structure is carried out to find an element from the list of elements stored.

Searching is of two types:

1. Linear search
2. Binary search

In this chapter, we are going to focus entirely on linear search. Binary search will be explained in the next chapter of this tutorial.

### Linear Search

Linear search operation involves accessing each element of the list one by one in sequential manner and comparing if the the element is the desired element or not.

Three scenarios are possible considering n→number of elements:

1. The element may be traced in the first comparision in case the desired element is present at the very first location.
2. The element may be present somewhere between first and last location and that case (n+1)/2 comparision will be made.
3. The element may be present at last location and in that case n comparision would be required.

Refer the diagram given below:

From the above, we can see:

• 65 is the item to be searched.
• Following linear search technique, search would start from index 0. Here 12==65 is not true
• Next element at index 1 will be picked. Here 9==65 is false
• Next element at index 2 will be picked. Here 67==65 is false
• Next element at index 3 will be picked. Here 88==65 is false
• Next element at index 4 will be picked. Here 65==65 is true
• Location at which element is found is printed. Here element is found at 4.
• Exit the search operation.

### Algorithm for Linear search

Suppose arr[n] is the linear array. item is the element to be searched.

1. Set location = -1
2. Iterate array till i
3. Validate if arr[i]==item
4. set location=i;
5. Apply break to exit the loop
6. if loc>=0 then Print the location