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. |