In this article, you will learn to write a C program that implement two search algorithms – Linear Search and Binary Search Algorithm using C switch statement.
The purpose is not to explain the algorithm, but to show you the implementation and working of these two search algorithms.
This program is written on Turbo C++ version 3.0, but you can use any other standard C compiler to code and run this program. It is intended for intermediate learners of C language. Check the following sections for more details.
- Learn Implementation of Bubble Sort Algorithm
- Learn Implementation of Insertion Sort Algorithm
- Find Maximum and Minimum Using Pointers.(Linear Search Method).
Problem Definition
The program implements two search algorithm – linear search and binary search. The linear search is probably the oldest search algorithm, it goes through each and every element of the unsorted array and look for the key, you are searching for. However, the binary search, look for an element by dividing the array into two half, then compare the key element with a calculated mid value. If key is less than or equal to mid value, go left half and keep doing the same thing all over again. If the key is greater than the mid value, go to the right half of array, and perform the same steps again.
The binary search is faster, but it requires that the array is already sorted in ascending order or descending order. Otherwise it won’t work.
Program Code
/* Program to implement linear search and Binary search */
#include <stdio.h>
#include <stdlib.h>
main()
{
/* Declare variables - array_of_number,search_key,i,j,low,high*/
int array[100],search_key,i,j,n,low,high,location,choice;
void linear_search(int search_key,int array[100],int n);
void binary_search(int search_key,int array[100],int n);
clrscr();
/* read the elements of array */
printf("ENTER THE SIZE OF THE ARRAY:");
scanf("%d",&n);
printf("ENTER THE ELEMENTS OF THE ARRAY:\n");
for(i=1;i<=n;i++)
{
scanf("%d",&array[i]);
}
/* Get the Search Key element for Linear Search */
printf("ENTER THE SEARCH KEY:");
scanf("%d",&search_key);
/* Choice of Search Algorithm */
printf("___________________\n");
printf("1.LINEAR SEARCH\n");
printf("2.BINARY SEARCH\n");
printf("___________________\n");
printf("ENTER YOUR CHOICE:");
scanf("%d",&choice);
switch(choice)
{
case 1:
linear_search(search_key,array,n);
break;
case 2:
binary_search(search_key,array,n);
break;
default:
exit(0);
}
getch();
return 0;
}
/* LINEAR SEARCH */
void linear_search(int search_key,int array[100],int n)
{
/*Declare Variable */
int i,location;
for(i=1;i<=n;i++)
{
if(search_key == array[i])
{
location = i;
printf("______________________________________\n");
printf("The location of Search Key = %d is %d\n",search_key,location);
printf("______________________________________\n");
}
}
}
/* Binary Search to find Search Key */
void binary_search(int search_key,int array[100],int n)
{
int mid,i,low,high;
low = 1;
high = n;
mid = (low + high)/2;
i=1;
while(search_key != array[mid])
{
if(search_key <= array[mid])
{
low = 1;
high = mid+1;
mid = (low+high)/2;
}
else
{
low = mid+1;
high = n;
mid = (low+high)/2;
}
}
printf("__________________________________\n");
printf("location=%d\t",mid);
printf("Search_Key=%d Found!\n",search_key);
printf("__________________________________\n");
}Output
The output of the above program is given below. The user first enters the array size and array elements. But if he wants to use the binary search, the user must enter sorted values.
Then the user is given two choice of search algorithms – linear search and binary search. This part is implemented using C switch-case statements.
ENTER THE SIZE OF THE ARRAY:6
ENTER THE ELEMENTS OF THE ARRAY:
45
6
86
23
64
77
ENTER THE SEARCH KEY:86
____________________
1. LINEAR SEARCH
2. BINARY SEARCH
____________________
ENTER YOUR CHOICE:2
_____________________________________________
Location =3 Search_Key = 86 Found!