# Search Techniques - Linear Search and Binary Search

Searching refers to finding an element in a list of elements. In this article, I am going to discuss about the two search techniques linear search and binary search with their corresponding algorithms and C programs.

## Linear Search

Linear Search is the simplest search technique. The procedure of linear search is as follows. The entire list is compared with the key element i.e. the element to be found and the search stops when the element is found. To understand linear search clearly, let us take an example.

Consider the list 23, 56, 22, 12, 90, 57, 78, 24, 88, 45, 70, 67, 34.

Consider the key element as 90.

Compare 23 & 90 (No Match - Continue)

Compare 56 & 90 (No Match - Continue)

Compare 22 & 90 (No Match - Continue)

Compare 12 & 90 (No Match - Continue)

Compare 90 & 90 (Match - End Linear Search)

### Algorithm for Linear Search

**LinearSearch**

Input: An array a[1], a[2], …… a[n] and the key K.Output: The index of the array element which is equal to key K.

1 : START

2 : for i=1 to n do

3 : if(a[i]=K) then

4 : return i

5 : endIf

6 : endFor

7 : return 0

8 : STOP

### C Program for Linear Search

**Program**

#include<stdio.h>

#include<conio.h>

void main(void)

{

int size,list[25],key,i;

clrscr();

printf("\n Enter the number of elements : ");

scanf("%d",&size);

printf("\n Enter the list of elements : ");

for(i=1;i<=size;i++)

scanf("%d",&list[i]);

printf("\n Enter the element to search : ");

scanf("%d",&key);

for(i=1;i<=size;i++)

{

if(list[i]==key)

printf("\n Element found at position %d",i);

}

printf("\n Search Complete");

getch();

}

**Output**

Enter the number of elements : 13

Enter the list of elements : 23 56 22 12 90 57 78 24 88 45 70 67 34

Enter the element to search : 90

Element found at position 5

Search Complete

Time complexity for linear search is O(1) in the best case when the first element is equal to the key, O(n) in the average and worst cases when element not at the start or the last element is equal to the key respectively. Space complexity for linear search is O(n) in best, worst and average cases.

## Binary Search

As linear search takes a lot of time for large lists, binary search is introduced. The procedure of binary search is as follows. First, sort the list of elements and find the middle element. Compare the key element i.e. the element to be found with the middle element. If key is greater, apply binary search on the elements right to the middle element. If middle element is greater, apply binary search on the elements left to the middle element. To understand binary search clearly, let us take an example.

Consider the list 23, 56, 22, 12, 90, 57, 78, 24, 88, 45, 70, 67, 34.

Consider the key element as 90.

Sort the list to obtain 12, 22, 23, 24, 34, 45, 56, 57, 67, 70, 78, 88, 90.

Middle element is the 7th element i.e. 56.

Apply binary search on the list right (57, 67, 70, 78, 88, 90) to the middle element (90>56)

Middle element is the 3rd element i.e. 70.

Apply binary search on the list right (78, 88, 90) to the middle element (90>56)

Middle element is 2nd element i.e. 88.

Apply binary search on the list right (90) to the middle element (90>88)

Only one element is present and it is equal to 90.

Match - End Binary Search.

### Algorithm for Binary Search

**BinarySearch**

Input: A sorted array a[1], a[2], …… a[n] and the key K.Output: The index of the array element which is equal to key K.

1 : START

2 : start=1

3 : stop=n

4 : middle=(start+stop)/2

5 : while(start<=stop) do

6 : if(list[middle]<K) then

7 : start=middle+1

8 : else if(list[middle]=K) then

9 : return middle

10 : else

11 : stop=middle-1

12 : endIf

13 : endWhile

14 : return 0

15 : STOP

### C Program for Binary Search

**Program**

#include<stdio.h>

#include<conio.h>

void main(void)

{

int size,list[25],key,i,start,stop,middle;

clrscr();

printf("\n Enter the number of elements : ");

scanf("%d",&size);

printf("\n Enter the list of elements : ");

for(i=0;i<size;i++)

scanf("%d",&list[i]);

printf("\n Enter the element to search : ");

scanf("%d",&key);

start=0;

stop=size-1;

middle=(start+stop)/2;

while(start<=stop)

{

if(list[middle]<key)

start=middle+1;

else if(list[middle]==key)

{

printf("\n Element found at position %d",middle+1);

break;

}

else

stop=middle-1;

middle=(start+stop)/2;

}

printf("\n Search Complete");

getch();

}

**Output**

Enter the number of elements : 13

Enter the list of elements : 23 56 22 12 90 57 78 24 88 45 70 67 34

Enter the element to search : 90

Element found at position 5

Search Complete

Time complexity for above binary search is O(1), O(logn), O(logn) in best case, average case, worst case respectively. Space complexity for above binary search is O(1) in best, worst and average cases.