Searching -Linear Search Algorithm

Searching in the data structure can be done by applying searching algorithms to check for or extract an element from any form of stored data structure.

These algorithms are classified according to the type of search operation they perform, such as:

• Sequential search
  The list or array of elements is traversed sequentially while checking every component of the set.

  For example – Linear Search.

• Indexed Search

• Interval Search
  The interval search includes algorithms that are explicitly designed for searching in sorted data structures. In terms of efficiency, these algorithms are far better than linear search algorithms.

  Example- Logarithmic Search, Binary search.

These methods are evaluated based on the time taken by an algorithm to search an element matching the search item in the data collections and are given by,

• The best possible time
• The average time
• The worst-case time

The primary concerns are with worst-case times, which provide guaranteed predictions of the algorithm’s performance and are also easier to calculate than average times.

To illustrate concepts and examples in this article, we are assuming ‘n’ items in the data collection in any data format. To make analysis and algorithm comparison easier, dominant operations are used. A comparison is a dominant operation for searching in a data structure, denoted by O() and pronounced as “big-Oh” or “Oh.”

There are numerous searching algorithms in a data structure such as linear search, binary search, interpolation search, sublist search, exponential search, jump search, Fibonacci search, the ubiquitous binary search, recursive function for substring search, unbounded, binary search, and recursive program to search an element linearly in the given array. The article includes linear search, binary search, and interpolation search algorithms and their working principles.

Linear Search Algorithm

In this article, we will discuss the Linear Search Algorithm. Searching is the process of finding some particular element in the list. If the element is present in the list, then the process is called successful, and the process returns the location of that element; otherwise, the search is called unsuccessful.

Two popular search methods are Linear Search and Binary Search. So, here we will discuss the popular searching technique, i.e., Linear Search Algorithm.

Linear search is also called as sequential search algorithm. It is the simplest searching algorithm. In Linear search, we simply traverse the list completely and match each element of the list with the item whose location is to be found. If the match is found, then the location of the item is returned; otherwise, the algorithm returns NULL.

It is widely used to search an element from the unordered list, i.e., the list in which items are not sorted. The worst-case time complexity of linear search is O(n).

The steps used in the implementation of Linear Search are listed as follows -

• First, we have to traverse the array elements using a for loop.
• In each iteration of for loop, compare the search element with the current array element, and -
  • If the element matches, then return the index of the corresponding array element.
  • If the element does not match, then move to the next element.
• If there is no match or the search element is not present in the given array, return -1.

Now, let's see the algorithm of linear search.

Algorithm

1. Linear Search ( Array A, Value x)
   
   Step 1: Set i to 1
   Step 2: if i > n then go to step 7
   Step 3: if A[i] = x then go to step 6
   Step 4: Set i to i + 1
   Step 5: Go to Step 2
   Step 6: Print Element x Found at index i and go to step 8
   Step 7: Print element not found
   Step 8: Exit

Working of Linear search

Now, let's see the working of the linear search Algorithm.

To understand the working of linear search algorithm, let's take an unsorted array. It will be easy to understand the working of linear search with an example.

Let the elements of array are -

Let the element to be searched is K = 41

Now, start from the first element and compare K with each element of the array.

The value of K, i.e., 41, is not matched with the first element of the array. So, move to the next element. And follow the same process until the respective element is found.

Now, the element to be searched is found. So algorithm will return the index of the element matched.

Linear Search complexity

Now, let's see the time complexity of linear search in the best case, average case, and worst case. We will also see the space complexity of linear search.

1. Time Complexity

Case	Time Complexity
Best Case	O(1)
Average Case	O(n)
Worst Case	O(n)

• Best Case Complexity - In Linear search, best case occurs when the element we are finding is at the first position of the array. The best-case time complexity of linear search is O(1).
• Average Case Complexity - The average case time complexity of linear search is O(n).
• Worst Case Complexity - In Linear search, the worst case occurs when the element we are looking is present at the end of the array. The worst-case in linear search could be when the target element is not present in the given array, and we have to traverse the entire array. The worst-case time complexity of linear search is O(n).

The time complexity of linear search is O(n) because every element in the array is compared only once.

2. Space Complexity

Space Complexity: The space complexity of linear search is O(1).

Implementation of Linear Search

Now, let's see the programs of linear search in different programming languages.

Program: Write a program to implement linear search in C language.

#include <stdio.h>  
int linearSearch(int a[], int n, int val) {  
  // Going through array sequencially  
  for (int i = 0; i < n; i++)  
    {  
        if (a[i] == val)  
        return i+1;  
    }  
  return -1;  
}  
int main() {  
  int a[] = {70, 40, 30, 11, 57, 41, 25, 14, 52}; // given array  
  int val = 41; // value to be searched  
  int n = sizeof(a) / sizeof(a[0]); // size of array  
  int res = linearSearch(a, n, val); // Store result  
  printf("The elements of the array are - ");  
  for (int i = 0; i < n; i++)  
  printf("%d ", a[i]);   
  printf("\nElement to be searched is - %d", val);  
  if (res == -1)  
  printf("\nElement is not present in the array");  
  else  
  printf("\nElement is present at %d position of array", res);  
  return 0;  
} 

Output

Indexed Search

Index search is special search. This search method is used to search a record in a file. Searching a record refers to the searching of location loc in memory where the file is stored. Indexed search searches the record with a given key value relative to a primary key field. This search method is accomplished by the use of pointers.

Index helps to locate a particular record with less time. Indexed sequential files use the principal of index creation.

For Example, Directory, book etc. In this type of file organization, the records are organized in a sequence and an index table is used to speed up the access to records without searching the entire file. The records of the file may be sorted in random sequence but the index table is in started sequence on the key field. Thus the file can be processed randomly as well as sequentially.

Advantage

• More efficient.
• Time required is less.

 

"Sequential indexed search" diagram explanation:

Code:

// C program for Indexed Sequential Search

#include

#include

void indexedSequentialSearch(int arr[], int n, int k)

{

int elements[20], indices[20], temp, i;

int j = 0, ind = 0, start, end;

for (i = 0; i < n; i += 3) {

// Storing element

elements[ind] = arr[i];

// Storing the index

indices[ind] = i;

ind++;

}

if (k < elements[0]) {

printf("Not found");

exit(0);

}

else {

for (i = 1; i <= ind; i++)

if (k < elements[i]) {

start = indices[i - 1];

end = indices[i];

break;

}

}

for (i = start; i <= end; i++) {

if (k == arr[i]) {

j = 1;

break;

}

}

if (j == 1)

printf("Found at index %d", i);

else

printf("Not found");

}

// Driver code

void main()

{

int arr[] = { 6, 7, 8, 9, 10 };

int n = sizeof(arr) / sizeof(arr[0]);

// Element to search

int k = 8;

indexedSequentialSearch(arr, n, k);

}

Copy

Output:

Found at index 2