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

## 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)
{
}

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)
{
}

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)
{
```Sample Input: