Searching is the process of finding element in a given list. In this process we check item is available in given list or not.

**Type of searching**

- Internal search
- External search

**Internal Search**: In this search, Searching is performed on **main or primary memory.****External Search**: In this search, Searching is performed in **secondary memory.**

There are basically three types of searching techniques:

Linear or sequential search

Binary search

Interpolation search

**Linear/ Sequential Search****Linear/Sequential **searching is a searching technique to find an item from a list until the particular item not found or list not reached at end. We start the searching from 0th index to N-1 index in a sequential manner, if particular item found, returns the position of that item otherwise return failure status or -1.

10 | 14 | 19 | 26 | 27 | 31 | 33 | 35 | 42 | 44 |

**Linear**

**Search**

**Algorithm**

Linear Search ( Array A, Value x)

Step 1: Set i to 1

Step 2: if i > n then go to step 7

Step 3: if A[i] = x then go to step 6

Step 4: Set i to i + 1

Step 5: Go to Step 2

Step 6: Print Element x Found at index i and go to step 8

Step 7: Print element not found

Step 8: Exit

```
#include <stdio.h>
/*Function to search item from list*/
int LinearSearch(int ele[], int n, int item)
{
int pos = -1,k;
for( k = 0; k < n; k++ )
{
if( ele[k] == item )
{
pos = k;
break;
}
}
return pos;
}
void main()
{
int ele[10],k,n,item,pos;
printf("Enter no of elements : ");
scanf("%d",&n);
printf("\nEnter Items : \n");
for( k = 0; k < n; k++)
scanf("%d",&ele[k]);
printf("\n\nEnter Item To Be Searched : ");
scanf("%d",&item);
pos = LinearSearch(ele, n, item);
if( pos >= 0 )
printf("\nItem Found At Position : %d\n",pos+1);
else
printf("\nItem Not Found In The List\n");
getch();
}
```

**Binary Search**

For a binary search to work, it is mandatory for the target array to be sorted. We shall learn the process of binary search with a pictorial example. The following is our sorted array and let us assume that we need to search the location of value 31 using binary search.

10 | 14 | 19 | 26 | 27 | 31 | 33 | 35 | 42 | 44 |

First, we shall determine half of the array by using this formula −

mid = low + (high – low) / 2

Here it is, 0 + (9 – 0 ) / 2 = 4 (integer value of 4.5). So, 4 is the mid of the array.

10 | 14 | 19 | 26 | 27 | 31 | 33 | 35 | 42 | 44 |

Now we compare the value stored at location 4, with the value being searched, i.e. 31. We find that the value at location 4 is 27, which is not a match. As the value is greater than 27 and we have a sorted array, so we also know that the target value must be in the upper portion of the array.

31 | 33 | 35 | 42 | 44 |

We change our low to mid + 1 and find the new mid value again.

low = mid + 1

mid = low + (high – low) / 2

Our new mid is 7 now. We compare the value stored at location 7 with our target value 31.

10 | 14 | 19 | 26 | 27 | 31 | 33 | 35 | 42 | 44 |

The value stored at location 7 is not a match, rather it is more than what we are looking for.

So, the value must be in the lower part from this location.

31 | 33 |

Hence, we calculate the mid again. This time it is 5.

31 | 33 |

We compare the value stored at location 5 with our target value. We find that it is a match.

31 |

We conclude that the target value 31 is stored at location 5.

Binary search halves the searchable items and thus reduces the count of comparisons to be made to very less numbers.**Algorithm**

BINARY SEARCH (LIST, N, ITEM, LOC, LOW, MID, HIGH)

- Set LOW := 1; LOW := N;
- Repeat step a to d while LOW <= HIGH and ITEM != LIST(MID)

a. Set MID := (LOW + HIGH)/2

b. If ITEM = LIST(MID), then

i. Set LOC := MID

ii. Return

c. If ITEM < LIST(MID) then

i. Set HIGH := MID – 1;

d. Otherwise

i. Set LOW := MID + 1; - SET LOC := NULL
- return

```
#include <stdio.h>
/*Function to search item from sorted list*/
int BinarySearch(int ele[], int n, int item)
{
int pos = -1,k,low,mid,high;
low = 0;
high = n-1;
while( low <= high )
{
mid = (low + high)/2;
if( ele[mid] == item )
{
pos = mid ;
break;
}
else if( item > ele[mid] )
low = mid + 1;
else
high = mid - 1;
}
return pos;
}
void main()
{
int ele[10],k,n,item,pos;
printf("Enter no of elements : ");
scanf("%d",&n);
printf("\nEnter Items : \n");
for( k = 0; k < n; k++)
scanf("%d",&ele[k]);
printf("\n\nEnter Item To Be Searched : ");
scanf("%d",&item);
pos = BinarySearch(ele, n, item);
if( pos >= 0 )
printf("\nItem Found At Position : %d\n",pos+1);
else
printf("\nItem Not Found In The List\n");
getch();
}
```

Difference between Linear Search and Binary Search

Linear Search | Binary Search |

Sorted list is not required. | Sorted list is required. |

It can be used in linked list implementation. | It cannot be used in liked list implementation. |

It is suitable for a list changing very frequently. | It is only suitable for static lists, because any change requires resorting of the list. |

The average number of comparison is very high. | The average number of comparison is relatively slow. |

**Interpolation Search**

An Interpolation Search is a type of searching algorithm. An Interpolation Search is an improvement over Binary Search for scenarios where the values in a sorted array are uniformly distributed. Binary Search goes to the middle element to check. On the other hand, Interpolation Search may go to different locations according to the value of the key being searched. For example, if the value of the key is close to the last element, Interpolation Search is likely to start search toward the end side.

This technique is used if the items to be searched are uniformly distributed between the first and the last location. This technique is a simple modification in the binary search when MID is calculated.

Mid = low + (high – low) * ((item – LIST[low]) / (LIST[high] – LIST[low]));

**Advantages**

- If the items are uniformly distributed, the average case time complexity is log2(log2(n)).
- It is considered improvement in binary search.
**Disadvantages** - The calculation of mid is complicated. It increases the execution time.
- If the items are not uniformly distributed, interpolation search will have very poor behavior.
**Algorithm**

As it is an improvisation of the existing BST algorithm, we are mentioning the steps to search the ‘target’ data value index, using position probing −

Step 1 − Start searching data from middle of the list.

Step 2 − If it is a match, return the index of the item, and exit.

Step 3 − If it is not a match, probe position.

Step 4 − Divide the list using probing formula and find the new

midle.

Step 5 − If data is greater than middle, search in higher sub-list.

Step 6 − If data is smaller than middle, search in lower sub-list.

Step 7 − Repeat until match.

**Pseudocode**

```
A → Array list
N → Size of A
X → Target Value
Procedure Interpolation_Search()
Set Lo → 0
Set Mid → -1
Set Hi → N-1
While X does not match
if Lo equals to Hi OR A[Lo] equals to A[Hi]
EXIT: Failure, Target not found
end if
Set Mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])
if A[Mid] = X
EXIT: Success, Target found at Mid
else
if A[Mid] < X
Set Lo to Mid+1
else if A[Mid] > X
Set Hi to Mid-1
end if
end if
End While
End Procedure
```