Searching Algorithm
In this tutorial we will learn about Linear Search algorithm.
For better search algorithm check out Binary Search tutorial.
In this searching technique we compare the elements of the array one-by-one with the key element we are looking for.
It is a very simple searching algorithm but it takes a lot of time.
/** * a[0:n-1] is an array of n elements. key is the element being searched. */ LinearSearch(a,n,key) Begin for i = 0 to n-1 by 1 do if a[i] == key then return i; //returning index of the array endif endfor return -1; //key not found End
In the best case scenario we will get the element we are searching for in 1 comparison.
That is, the first element is the answer. So, order will be O(1).
In the worst case scenario the element we are looking for is either at the last position or not present.
So, we have to make n comparisons to come to a conclusion. So, order is O(n).
n
#include <stdio.h> //function declaration int linearSearch(int *a, int n, int key); int main(){ //variable declaration int arr[5], i, key; //input printf("Enter the array elements: "); for(i = 0; i < 5; i++) scanf("%d", &arr[i]); printf("Enter key: "); scanf("%d", &key); //search i = linearSearch(arr, 5, key); //output if(i == -1) printf("Key not found.\n"); else printf("Key at index: %d\n", i); return 0; } //function definition int linearSearch(int *a, int n, int key){ int i; for(i = 0; i <= n-1; i++){ if(a[i] == key) return i; } return -1; }