Linear Search in detail

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₀, a₁, a₂, …, 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).