Searching

Searching in an array

Searching is a very common process in computer science. The objective of searching to find an element in the given array. The goal of a searching process to find the element as soon as possible, because speed plays an important role that searching is useful or not.

There are various types of searching in which each searching has its own benefits. In this article, we discuss two important types of searching.

  1. Linear Searching
  2. Binary Searching

Linear Searching

The objective of searching to find an element item in an array arr. if found then return the found position otherwise inform the user that item not found.

Linear search works with a simple technique. In this technique to find the element item in an array match item with each element, if found then return the position and stop searching immediately.

It item not found till the end of the array, then report the user that item not found.

Linear search program

Objective

Find an element item in an array arr of size n using a function. if the item found in the array the print the element found with the element position otherwise inform the user that Item not found.

Program

#include<stdio.h>
int linear_search(int arr[],int n,int item) {
	int i;
	for(i = 0; i < n; i++) {
		if(arr[i] == item) {
			return i;
		}
	}
	return -1;
}
int main() {
	int arr[20];
	int i,n;
	int item,pos;
	
	printf("Enter how many element, (max:20): ");
	scanf("%d",&n);
	
	//Array input
	for(i = 0; i < n; i++) {
		printf("Enter element %d: ",i+1);
		scanf("%d",&arr[i]);
	}
	
	//Item to search
	printf("Enter the item to input: ");
	scanf("%d",&item);
	
	pos = linear_search(arr,n,item);
	
	if(pos != -1) {
		printf("Item found at index %d",pos);
	}else {
		printf("Item not found");
	}
	return 0;
}

Output

Enter how many element, (max:20): 5
Enter element 1: 6
Enter element 2: 4
Enter element 3: 8
Enter element 4: 2
Enter element 5: 7
Enter the item to input: 8
Item found at index 2
Enter how many element, (max:20): 5
Enter element 1: 2
Enter element 2: 6
Enter element 3: 4
Enter element 4: 5
Enter element 5: 9
Enter the item to input: 11
Item not found

Explanation

  • As shown in the above example, to search the element item linear_search() function is created.
  • In linear_search() function array and item is passed. As we have already learned to pass the array name and size is passed.
  • As shown in the above code in linear_search() function we iterate the loop from 0 to n to access the array element and match each array element arr[i] with the item.
  • If the item found we return the position i.
  • If control jumps out of the loop means the item does not match with any array item then return a position(index = -1) that is not an array.
  • Finally, in main() function, we match the pos with -1 and if the position is -1 then item not found otherwise prints item found at position pos.

Analysis of linear search

  1. If the item is matched with the first element of the array then only one compare is performed and the loop executes only once.
  2. If item not found or found at last position then n(size of an array) compares are performed and loop executes n times.
  3. Min Compare: 1
  4. Max Compare: N

So the objective is to analyze the linear search algorithm is to find the Maximum compare. So as in the linear search algorithm maximum N compares are needed. In Programming terminology, it is represented as O(N)

O(N) is called Big oh Notation or Order of algorithm which represents the upper bound of the algorithm.

Means if the array size is 100 then maximum 100 compares needed and if the array size is 10000 then 10000 compares performed.

Menas the time of linear search grows as the size of the array grows. So this is a very slow time