SEARCHING
The process of finding the location of a specific data item or record with a given key value or finding the locations of all records, which satisfy one or more conditions in a list, is called "Searching". If the item exists in the given list then search is said to be successful otherwise if the element if not found in the given list then search is said to be unsuccessful.
There are two popular methods for searching the array elements: linear search and binary search.
Linear Search:
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.
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.
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 -
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:
The algorithm is called linear search because it's complexity/efficiency can be expressed as a linear function ie., the number of comparisons to find a target increases linearly as the size of the data.
Linear search provide complexity for finding an element in an array because linear search is a step-by-step process, in which specific element is compared with each element of array.
Best Case
In the best case, the desired element is present in the first position of the array, Le, only one comparison is made. So T(n) = O (1).
Average Case
Here we asume that ITEM does appear, and that is equally likely to occur at any position in the array. Accordingly the number of comparisons can be any of the number 1, 2, 3, n and each number occurs with the probability p = 1 / n
Then T(n) =1. (1 / n) +2.(1/n)+3.(1/n)...+n.(1/n).
=( 1 + 2 + 3 +...+n).(1/n)
Worst Case
Clearly the worst case occurs when ITEM is the last element is the array or is not there at all. In either situation we have T(n) = n + 1 Accordingly T(n) = O(n + 1) is the worst case complexity of the linear search algorithm.
#include <stdio.h>
int linearSearch(int a[], int n, int val) {
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};
int val = 41;
int n = sizeof(a) / sizeof(a[0]);
int res = linearSearch(a, n, val);
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:
Applications of Linear Search Algorithm:
- Unsorted Lists: When we have an unsorted array or list, linear search is most commonly used to find any element in the collection.
- Small Data Sets: Linear Search is preferred over binary search when we have small data sets with
- Searching Linked Lists: In linked list implementations, linear search is commonly used to find elements within the list. Each node is checked sequentially until the desired element is found.
- Simple Implementation: Linear Search is much easier to understand and implement as compared to Binary Search or Ternary Search.
Advantages of Linear Search Algorithm:
- Linear search can be used irrespective of whether the array is sorted or not. It can be used on arrays of any data type.
- Does not require any additional memory.
- It is a well-suited algorithm for small datasets.
Disadvantages of Linear Search Algorithm:
- Linear search has a time complexity of O(N), which in turn makes it slow for large datasets.
- Not suitable for large arrays.
