# Interview Questions

# Linear Search in detail

- June 29, 2013
- Posted by: Kamal Rawat
- Category: Algorithms College

Linear search or Sequential search is a method for finding a particular value in a linear list of values (Array or Linked List). It is done by checking each of its elements, one at a time in list, until the desired one is found or the list is exhausted.

**Problem definition (for array)**

Given an Array of numbers a_{0}, a_{1}, a_{2}, …, a_{n}. and a number x. Write a function which will return i, such that (a_{i} == x). If x is not in the Array, then return -1 (which means “Not Found”).

**For Example:** If Array is as given below and x = 5 (element to be searched)

Then the function should return 3 (because 5 is at index 3)

The signature of function is:

int search(int *arr, int n, int x);

**Algorithm:**

Search for each element in the array starting from 0, 1, 2, … and continue till either arr[i] == x or the array is exhausted.

**Code:**

/** Function searches data in an array arr of size n. * If data is present in arr, it returns index of first occurrence in array. * Else returns -1 to indicate that data is not found in array. */ int linearSearch(int * arr, int n, int data) { for(int i=0; i<n; i++) { if(arr[i] == data) return i; } return -1; }

**Time Complexity:**

**Best case:** O(1) – When element is found at the first position (it requires only one check)

**Worst Case:** O(n) – If element is not fount in the list. Then function will check all the n elements.

**Average Case:** O(n) – requires n/2 check.

**Linear Search in Linked List**

We cannot search in the linked list using Binary search because element at index i (arr[i]) cannot be found using constant time. Hence, linear search is the only option to search an element in a linked list.

int search(Node* head, int x) { int nodeNum = 0; while(head != NULL) { if(head->data == x) return nodeNum; nodeNum++; head = head->next; } return -1; }

**Variations:**

Following are the variations of linear search on arrays and linked list.

**1. Search for first occurrence of element from end of the list**

For array this is easy, we just need to modify the for loop to check from the last element till the first element. The loop

for(int i=0; i<n; i++)

Will be replaced with

for(int i=n-1; i>=0; i--)

and rest everything will remain the same.

For linked list, it will be difficult because there is no way to back track in a singly linked list (can’t move in the back ward direction). One way to do this is to

- reverse the list
- search in the reversed list
- reverse the list against

Another way is by using tail-recursion.

int search(Node* head, int x, int index=0) { if(head == NULL) return -1; int retVal = search(head->next, x, index+1); if( retVal == -1) { if(head->data == x) return index; } return retVal; }

**2. Printing indexes of all occurrences of data**

Print all the positions where x is present in the array. For example, if we are searching for 5 in the below array:

2 4 5 1 5 6 7 5 9 0 1

Then the output should be all the positions where 5 is present (2 is at position 0)

2 4 7

There is no best case for this variation, because we have to traverse the entire array (or linked list) in any case.

// Searching for all occurrences in forward direction: for(int i=0; i<n; i++) { if(arr[i] == x) cout<<"Element Found at position: "<<i; }

Searching in backward direction for all occurrences:

// Searching for all occurrences in forward direction: for(int i=n-1; i>=0; i++) { if(arr[i] == x) cout<<"Element Found at position: "<<i; }

Similarly it can be done for linked list also (don’t return the index, just print it and move forward).

Time complexity of all the functions above is O(n).