# Explore hunderds of solved example topic wise.

## 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.

### 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;
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 {
}
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
```

#### 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