# Linear Search

Posted by Anoop Nair on September 4, 2017

## What is Searching ?

In Data Structures searching refers to finding the location of a data element or printing some message if data element is not found.
Linear search is the simplest meathod of searching a data element ITEM in a linear array ARR[ ]. It follows the simple method of comparing each value of the ARR[ ] to ITEM, if the value is found the search is successful and we get the index value of the location else a message " Element not found" is displayed.

#### Complexity of Linear Search

Best Case Its when we get the ITEM at ARR so complexity is ` O(1) `.

Average case The average number of comparisons required to find the ITEM in ARR[ ] is equal to half the number of element in array. So it depends on the no. of elements n hence the complexity ` O(n)`.

Worst Case The worst case when we have to search the entire array so the complexity is ` O(n) `here n is the size of array

Linear Search Program In C

```    ```
void main(){
int arr, value , i,index = 0, n, count;
printf("Enter the size of array \n");
scanf("%d", &n);

// getting user input for array

printf("Enter the values of array \n");
for(i=0; i< n ; i++){
scanf("%d", &arr[i]);
}
printf("Enter the value to be searched in array");
scanf("%d", &value);

// comparing each element of array with the value we want to search

for(i=0 ; i< n ; i++){
if(arr[i] == value){
count = 1 ;
index = i;
break;
}
else{
count = 0;
}
}
if(count == 0){
}
else{
printf("Element Found At index \t %d" , index);
}
}
```
```

Output Linear Search Program In Java

```    ```
package basics;
import java.io.* ;
public class LinearSearch {
public static void main(String arg[]) throws IOException{
int i, n , value;
int flag = 0 , index = 0;
int arr[] = new int;
System.out.println("Enter the size of array");

System.out.println("Enter the Values of the array");
for(i=0 ; i< n ; i++){

}
System.out.println("Enter the value to be searched in array");

for(i=0 ; i< n ; i++){
if(arr[i] == value ){
flag = 1;
index = i;
break;
}
else flag = 0 ;
}
if(flag == 1){
System.out.println("The value is present in Array and is at index \t" + index);
}
else{ 