Write a C or C++ Program to implement Linear or Sequential Search.

Linear Search is a very simple search algorithm. In sequential search, all elements are checked one by one. If a match is found then return the matched element’s index. Otherwise search till the end of the array or list.

How Linear Search Works ๐Ÿ“บ

Watch this video to understand how linear search works.


Steps ๐Ÿชœ

  1. Accept N numbers from the user and store them in an array nums. Next, display or print all these numbers.
  2. After that, accept key value that user wants to search.
  3. Pass array and the key value to a UDF (User Defined Function). This function will check each and every element of the array.
  4. If a match is found then it will return the index otherwise it will return -1 which indicates, element not found.
  5. Finally, display an appropriate message based on the returned value.

Code ๐Ÿ’ป

Learn Search in C++

Note: Some compilers may not support some built-in functions such as delay() and getch();

#include <iostream.h>
#include <stdio.h>
#include <conio.h>
#include <dos.h>
#include <stdlib.h>

// UDF for Linear Search
int linearSearch(int nums[], int k)
    for(int cnt = 0; cnt<10; cnt++)
	    if(k == nums[cnt])
	       return cnt;
    return -1;

void main()
    int nums[10], key;
    clrscr(); // clear the screen

    // accept elements from the user
    for(int cnt = 0; cnt<10; cnt++)
	    cout<<"Please enter the value"<<cnt+1<<": ";

    // print all the elements of the array or list
    cout<<"\nDisplaying all elements:"<<endl;
    for(cnt = 0; cnt<10; cnt++)
	    cout<<nums[cnt]<<" ";

    // print a message and accept the number(key) you want to search
    cout<<"\n\nPlease enter the number you want to search: ";

    // call linearSearch function which returns index
    int index = linearSearch(nums, key);

    if(index != -1) // if key element found
	    cout<<"\nKey value ("<<key<<") found at index "<<index<<".";
    else // if key element not found
	    cout<<"\nKey value ("<<key<<") not found.";

Example ๐Ÿ˜

Let’s assume, the user enters 10 values as 23, 11, 78, 61, 12, -1, 99, 21, 33 and 45. These values will be displayed to the user on console screen. After that, the user enters 33 as the key value.

Next, the key value is checked with all values of the array one by one until the match is found. Since, the key value 33 is there in the array, therefore the message will be displayed, “Key value (33) found at index 8“.

Let’s take another example, in which the user enters key value as 0 which we know is not there in the array. Thus, after checking with each and every value of the array, it will display “Key value (0) not found“.

In best-case scenario, the key value is present at the beginning of the array.
In worst-case scenario, is the key value is present at the end of the array.

This is how Linear Search works. For more Data Structures and Algorithms related posts, click here.