This is a C Program to implement Binary Search Algorithm.
Problem Description
We have to create a C Program which uses Binary search algorithm to predict that the element is present or not in the array. The user has to input a sorted array because binary search works on sorted array.
Expected Input and Output
1. Average Case: When the element to be searched is other than the middle element. For example:
If the input array is {1, 2, 3, 4, 5, 6}
and the key to be searched for is 6
then the expected output will be “Search Successful”.
Average case time complexity: O(log n).
2. Best Case: If the element to be searched is the middle element of the array. For example:
If the input array is {1, 5, 9}
and the key to be searched is 5,
then the expected output will be “Search Successful”.
Best case time complexity: O(1).
3. Worst Case: If the element to be searched for is not present in the array.
If the input array is {1, 3, 6, 8, 9}
and the key to be searched for is 4,
then the expected output will be “Search Unsuccessful”.
/*
* C program to accept N numbers sorted in ascending order
* and to search for a given number using Binary Search.
* Report success or failure.
*/
#include
void main()
{
int array[10];
int i, j, num, temp, keynum;
int low, mid, high;
printf(“Enter the value of num \n”);
scanf(“%d”, &num);
printf(“Enter the elements one by one \n”);
for (i = 0; i < num; i++)
{
scanf("%d", &array[i]);
}
printf("Input array elements \n");
for (i = 0; i < num; i++)
{
printf("%d\n", array[i]);
}
/* Bubble sorting begins */
for (i = 0; i < num; i++)
{
for (j = 0; j < (num - i - 1); j++)
{
if (array[j] > array[j + 1])
{
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
printf(“Sorted array is…\n”);
for (i = 0; i < num; i++)
{
printf("%d\n", array[i]);
}
printf("Enter the element to be searched \n");
scanf("%d", &keynum);
/* Binary searching begins */
low = 1;
high = num;
do
{
mid = (low + high) / 2;
if (keynum < array[mid])
high = mid - 1;
else if (keynum > array[mid])
low = mid + 1;
} while (keynum != array[mid] && low <= high);
if (keynum == array[mid])
{
printf("SEARCH SUCCESSFUL \n");
}
else
{
printf("SEARCH FAILED \n");
}
}Runtime Test Cases
1. Enter the value of num
6
Enter the elements one by one
1
2
3
4
5
6
Input array elements
1
2
3
4
5
6
Sorted array is...
1
2
3
4
5
6
Enter the element to be searched
6
SEARCH SUCCESSFUL
2. Enter the value of num
3
Enter the elements one by one
1
5
9
Input array elements
1
5
9
Sorted array is...
1
5
9
Enter the element to be searched
5
SEARCH SUCCESSFUL
3. Enter the value of num
5
Enter the elements one by one
1
3
6
8
9
Input array elements
1
3
6
8
9
Sorted array is...
1
3
6
8
9
Enter the element to be searched
4
SEARCH FAILED