What is linear search in C language?

What is meant by linear search in C?

We are aware that arrays are stored in memory in a linear manner, which means successive elements are stored alongside each other. So if we wish to search a thing from the array, the algorithm begins from an initial element and compares it with our essential item, then goes on next successive element till primary element is found or list endings.

For example, Consider an array of integers. You need to find and print the position of all of the elements with value. The linear search is based on matching notion, every element from the start to the end of the list, and then printing the position of the element when the condition is ‘True’.

Consider it as a means of finding your way at a phonebook. A Linear Search is beginning at the start, studying every name until you find everything you’re searching.

Time complexity of linear search

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

• Best case: O(1) – When an element is located at the initial position (it requires only one check).
• Worst Case: O(n) – If an element isn’t found in the list. Then the function will check all of the n elements.
• Typical Case: O(n) – requires an n/2 check.

Linear search is implemented using following approaches

• Begin from the first element of array list and one by one compare the element we’re searching for with each element of the array.
• When there’s a match involving the element we’re searching for the element of the array, return the index.
• When there’s absolutely no match between the element we’re searching for the element of the array, return -1.

Pseudocode for Linear Search

procedure linear_search (list, value)
 for each item in the list
   if match item == value
     return the item's location
   end if
 end for
end procedure

Implementing linear search program in c

#include<stdio.h>
#include<conio.h>
void main(){
  int list[20],size,i,sElement;
  printf("Enter the required list size: ");
  scanf("%d",&size);
  printf("Enter any %d numbers: ",size);
  for(i = 0; i < size; i++)
    scanf("%d",&list[i]);
    printf("Enter the element you want to Search: ");
    scanf("%d",&sElement);
    // Linear Search Logic
    for(i = 0; i < size; i++) {
      if(sElement == list[i]) {
        printf("Searched Element is found at %d index", i);
        break;
      }
   }
   if(i == size)
     printf("Searched element is not found in the list!!!");
     getch();
}

Output:

The time necessary to search an element with a linear search algorithm is dependent upon the size of this list. From the best-case situation, the element is present at the start of the list and the worst-case, it’s present at the conclusion.

The linear search time complexity is O(n), which makes it generally not as effective than binary search (O(log n)). However, while list items could be ordered from greatest to least and the probabilities seem as geometric distribution (f (x)=(1-p) x-1p, x=1,2). The linear search may possess the capability to be significantly faster than a binary search.

Why linear search is not efficient

There’s not any doubt that linear search is straightforward. But because it compares each element one by one, it’s time-intensive and therefore not so efficient. If we must locate a number out of, 1,000 and number is in the last place, then a linear search algorithm could turn out quite tedious.

Difference between linear search and binary search

• Binary Search necessitates the input information to be sorted; Linear Search does not.
• Binary Search necessitates an ordering contrast; Linear Search needs equality comparisons.
• Binary Search has complexity O(log n); Linear search has complexity O(n) as mentioned previously.
• Binary Search requires random access to this information; Linear Search needs sequential access (that can be quite significant — it means that a Linear Search can flow data of random size).

Advantages of a linear search

• When a key element matches the first element in the array, then linear search algorithm is best case because executing time of linear search algorithm is 0 (n), where n is the number of elements in an array.
• The list doesn’t have to sort. Contrary to a binary search, linear searching does not demand a structured list.
• Not influenced by insertions and deletions. Since the linear search doesn’t call for the list to be sorted, added elements can be inserted and deleted. As with other searching, algorithms might need to reorder the list after insertions or deletions. It might sometimes indicate a linear search will probably be more effective.
• An benefit of a linear search on a binary search is that the information has to be in sorted order to get a binary search.

Disadvantages of a linear search

• The drawback of a linear search is the fact that its time consuming for the enormous arrays.
• Inversely, slow searching of big lists. Every time a vital element matches the last element from the array or an essential element does not match any element Linear search algorithm is the worst case.