Linear Search in unordered array [with source code written in C and video example]

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.[1]
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) may be much more efficient. Linear search is usually very simple to implement, and is practical when the list has only a few elements, or when performing a single search in an unordered list. When many values have to be searched in the same list, it often pays to pre-process the latter in order to use a faster method. For example, one may sort the list and use binary search, or build any efficient search data structure from it.

This is an implementation of Linear Search in C Language, with Main structure.

Source Code


// © Codeido - www.codeido.com - Developed by Paolo Musolino

//Ricerca sequenziale in un array disordinato
#include <stdio.h>

int ricerca_Sequenziale(int a[], int n, int chiave)
{
	int i=0;
	
	while ((a[i]) && (i<n))
		   {
			   if (a[i]==chiave) 
			   {
				   return i;
				   
			   }
			   
			   if (i==n-1) 
			   {
				   return -1;
			   }
			   
			   if(a[i]!=chiave)
				   i++;
			   
		   }
	
}



int main ()
{
	int a[14]={5, 10, 11, 9, 7, 8, 4, 5, 7, 2, 45, 1, 4, 20};
	int ris_ricerca;
	ris_ricerca = ricerca_Sequenziale(a, 14, 20);
	printf("\n");
	
	if (ris_ricerca==-1) {
		printf("L'elemento cercato non è presente all'interno dell'array\n");
	}
	
	if (ris_ricerca>=0) {
		printf("L'elemento cercato si trova nella posizione %d ", ris_ricerca);
	}
	
	return 0;
}

Non-uniform probabilities
The performance of linear search improves if the desired value is more likely to be near the beginning of the list than to its end. Therefore, if some values are much more likely to be searched than others, it is desirable to place them at the beginning of the list.
In particular, when the list items are arranged in order of decreasing probability, and these probabilities are geometrically distributed, the cost of linear search is only O(1). If the table size n is large enough, linear search will be faster than binary search, whose cost is O(log n).[1]

Linear and Binary Searching

9 thoughts on “Linear Search in unordered array [with source code written in C and video example]

Leave a Reply to yilbasi turlari Cancel reply

Your email address will not be published. Required fields are marked *