Linear search | Search Algorithms | UVa Hints by Outsbook

Linear search

In computer science, linear search or sequential search is a method for finding a particular value in a list, that consists of checking every one of its elements, one at a time and in sequence, until the desired one is found.

Linear search is the simplest search algorithm; it is a special case of brute-force search. Its worst case cost is proportional to the number of elements in the list; and so is its expected cost, if all list elements are equally likely to be searched for. Therefore, if the list has more than a few elements, other methods (such as binary search or hashing) will be faster, but they also impose additional requirements.

Algorithm

 For each item in the list:
     if that item has the desired value,
         stop the search and return the item's location.
 Return null.

Example

Example 1: A list L = 10, 20, 100, 7, 98, 24, 27, 15. Find value V = 7.

Step 1:
    Compare V to 10 (value at position 0 of List L). 
    Not match. Go to next position.
Step 2:
    Compare V to 20 (value at position 1 of List L). 
    Not match. Go to next position.
Step 3:
    Compare V to 100 (value at position 2 of List L). 
    Not match. Go to next position.
Step 4:
    Compare V to 7 (value at position 3 of List L). 
    Ok match. We're done, we found V at position 3.
    Return position 3.

Example 2: A list L = 10, 20, 100, 7, 98, 24, 27, 15. Find value V = 57.

Step 1:
    Compare V to 10 (value at position 0 of List L). 
    Not match. Go to next position.
Step 2:
    Compare V to 20 (value at position 1 of List L). 
    Not match. Go to next position.
Step 3:
    Compare V to 100 (value at position 2 of List L). 
    Not match. Go to next position.
Step 4:
    Compare V to 7 (value at position 3 of List L). 
    Not match. Go to next position.
Step 5:
    Compare V to 98 (value at position 4 of List L). 
    Not match. Go to next position.
Step 6:
    Compare V to 24 (value at position 5 of List L). 
    Not match. Go to next position.
Step 7:
    Compare V to 27 (value at position 6 of List L). 
    Not match. Go to next position.
Step 8:
    Compare V to 15 (value at position 7 of List L). 
    Not match. We completed the whole list but do not find V (57) at list.
    Return null or "Not found message".

Pseudocode

Input: A list L and search value V

1  procedure LinearSearch(L,V):
2      for i=0 to L.length do:
3          if L[i]=V Then:
4              return i
5      return none

C code

#include <stdio.h>

int main()
{
    int n,numbers[100],search_number,i;

    scanf("%d",&n);
    for(i=0; i<n; i++)
    {
        scanf("%d",&numbers[i]);
    }
    scanf("%d",&search_number);
    for(i=0; i<n; i++)
    {
        if(numbers[i]==search_number)
        {
            printf("%d\n",i);
            break;
        }
    }

    if(i==n)
    {
        printf("Not found.\n");
    }

    return 0;
}

Sample Input:
8
10 20 100 7 98 24 27 15
100
Sample Output:
2

C++ code

#include <iostream>

using namespace std;

int main()
{
    int n,numbers[100],search_number,i;

    cin>>n;
    for(i=0; i<n; i++)
    {
        cin>>numbers[i];
    }
    cin>>search_number;
    for(i=0; i<n; i++)
    {
        if(numbers[i]==search_number)
        {
            cout<<i<<endl;
            break;
        }
    }

    if(i==n)
    {
        cout<<"Not found."<<endl;
    }

    return 0;
}

Sample Input:
8
10 20 100 7 98 24 27 15
7
Sample Output:
3

Java code

import java.util.*;

public class LinearSearch {

    public static void main(String args[]){
    	int n,search_number,i;
    	int numbers[]=new int[100];

    	Scanner in = new Scanner(System.in);

    	n = in.nextInt();
    	for(i=0;i<n;i++){
    		numbers[i] = in.nextInt();
    	}
    	search_number = in.nextInt();
    	for(i=0; i<n; i++)
    	{
        	if(numbers[i]==search_number)
        	{
            	    System.out.println(i);
            	    break;
        	}
    	}

    	if(i==n)
    	{
        	System.out.println("Not found.");
    	}
    }
}

Sample Input:
8
10 20 100 7 98 24 27 15
24
Sample Output:
5

Author

Shahin Mohammed Faroqe (ShamS)

I'm a programmer with more then 3 years of experience. I currently work for Howlader Corporation Ltd. I work primarily with C, C++, Java, .NET, and Mobile technologies, specializing in application development. I completed my B.Sc. in CSE from BGC Trust University Bangladesh.