Linear Search/ Sequential Search

Linear/Sequential Search

In computer science, linear search, also known as sequential search, is a method for locating a specific value in a list that involves verifying each of the list's members one by one until the desired one is discovered.

The simplest search algorithm is linear search. It's a type of brute-force search with a twist. Its worst-case cost is proportional to the list's amount of items.

The complexity of Linear Search Technique

• Time Complexity: O(n)

• Space Complexity: O(1)

Linear/ Sequential Search - Algorithm

Linear/ Sequential Search - Example

Search for 1 in the given array

Comparing the value of ith index with element to be search one by one until we get searched element or end of the array.

Element found at ith index, i=3

Example

#include<iostream>
using namespace std;

int linSearch(int a[], int size, int key) {
   for(int i = 0; i<size; i++) {
      if(a[i] == key) 
         return i; 
   }
   return -1; 
}

int main() {
   int n, skey, loc;
   cout << "Enter number of items: ";
   cin >> n;
   int arr[n]; 
   cout << "Enter items: " << endl;

   for(int i = 0; i< n; i++) {
      cin >> arr[i];
   }

   cout << "Enter which number to search in the list: ";
   cin >> skey;

   if((loc = linSearch(arr, n, skey)) >= 0)
      cout << "Item found at location: " << loc << endl;
   else
      cout << "Item is not found in the list." << endl;
}

Output

Enter number of items: 5
Enter items:
2 9 3 1 8
Enter which number/ to search in the list: 1
Item found at location: 3