C Programming Examples on Searching and Sorting
Posted by Superadmin on July 05 2019 12:46:10

 

 

C Programming Examples on Searching and Sorting

 

This section covers C programming examples on Searching and Sorting. Every example program includes the description of the program, C code as well as output of the program. All examples are compiled and tested on a Linux system. These examples can be simple C programs or advanced C programs. So, they are suitable for any user (dummies, beginners or advanced users).

 

Here is the listing of C programming examples on Searching and Sorting.

1. C Examples on Basic Sorting Algorithms

The C programs in this section demonstrate the Sort function. The Sort function sorts the elements in the range in a particular order. The different types of sorting methods are Bubble Sort, Selection Sort, Merge Sort and Quick Sort. Bubble Sort repeatedly sorts the adjacent elements if they are in wrong order. The Selection Sort finds the smallest element in the array and exchanges it with the element in the first position, it then finds the second smallest element and exchanges it with the element in the second position and continues this process until the entire list is sorted. The Merge Sort follows the Divide and Conquer rule where in it divides the input array into two halves, sorts the two halves and merges the two sorted halves. The Quick Sort selects an element as a pivot and partitions the given array around the pivot. The following C programs show the implementation of all the sorting methods mentioned above.

 

C Program to Sort N Numbers in Ascending Order using Bubble Sort
C Program to Sort the Array in an Ascending Order 
C Program to Sort the N Names in an Alphabetical Order
C Program to Implement Selection Sort Recursively
C Program to Implement Selection Sort Method using Functions 
C Program to Input Few Numbers & Perform Merge Sort on them using Recursion
C Program to Perform Quick Sort on a set of Entries from a File using Recursion

2. C Examples on Searching Algorithms

The C programs in this section demonstrate Searching Algorithm. The Searching Algorithm searches for the specified element in the given list. Binary Search and Linear Search are the commonly used searching algorithms. Linear Search Algorithm is used to find an item in the list. It starts searching for the item from the beginning of the list and continues till the end of the list until the item is found. The Binary Search Algorithm follows the Divide and Conquer strategy where in it finds the item from the sorted list of items. The following programs demonstrate Linear Search and Binary Search Algorithms and also searches for an element just by reading an array using recursion and without using recursion.

 

C Program to Read an Array and Search for an Element 
C Program to accept Sorted Array and do Search using Binary Search 
C Program using Recursion to Search an Element in Array
C Program to Perform Binary Search using Recursion
C Program to Implement Linear Search

3. C Examples on Special Sorting Algorithms

The C programs in this section illustrate other special Sorting Algorithms. These include Insertion Sort, Postman Sort, LSDRadix Sort, Heap Sort and Gnome Sort. Insertion Sort sorts the array by shifting the elements one by one. Postman Sort is a type of Bucket Sort in which the elements of an array are divided into buckets and then each bucket is sorted individually. LSDRadix Algorithm is used to sort the keys in integer representation order. Heap Sort is based on binary heap data structure and sorts elements similar to selection sort where the maximum element is placed at the end of the list. Gnome sort method sorts the items by comparing the current item with the previous item. If they are in order, move to the next item; If they are out of order, swap them and move to the previous item. If there is no previous item, move to the next item.

 

C Program to Implement Insertion Sort 
C Program to Implement Postman Sort Algorithm 
C Program to Sort an Integer Array using LSDRadix Sort Algorithm 
C Program to Sort an Array based on Heap Sort Algorithm 
C Program to Sort the Array Elements using Gnome Sort

4. C Examples on another Category of Special Sorting Algorithms

The C programs in this section demonstrates other special sorting algorithms. qSort is a function which performs quick sort. Pigeonhole Sort is a sorting technique that is used when the given range of keys is relatively small. An array of pigeonholes (buckets, chunks of memory) is reserved for each key value. The records from the unsorted list are scanned and copied into their respective pigeonholes based on their key values. Then, the contents of the pigeonholes are copied in sequence to the final destination. Cycle sort is an in-place, unstable sorting algorithm, a comparison sort that is optimal in view of the total number of writes to the original array. Odd-even sort is used for sorting on two-dimensional processor arrays. In Cocktail Sort, values “bubble” both directions through the array, because on each iteration the cocktail sort bubble sorts once forwards and once backwards. Bitonic sort is a comparison-based sorting algorithm that focuses on converting a random sequence of numbers into a bitonic sequence, one that monotonically increases, then decreases. Comb Sort is an in-place sort algorithm that repeatedly reorders different pairs of items. On each pass swaps pairs of items separated by the increment or gap, if needed, and reduce the gap. Stooge Sort is a recursive sorting algorithm.

 

C Program to Implement qsort using Function Pointers 
C Program to Implement Pigeonhole Sort 
C Program to Implement Cyclesort 
C Program to Implement Oddeven Sort 
C Program to Implement CockTail Sort 
C Program to Implement Bitonic sort 
C Program to Perform Comb Sort on Array of Integers
C Program to Implement Stooge Sort

5. C Examples on Pancake Sort, Bogo Sort and Shell Sort

The C programs in this section illustrate Pancake Sort, BogoSort and Shell Sort algorithms. In Pancake Sort, instead of individual elements being sorted, the only operation allowed is to “flip” one end of the list. Bogo Sort shuffles a list of values as long as they are not sorted. Shell sort is a generalization of insertion sort that allows the exchange of items that are far apart.

 

C Program to Implement Pancake Sort on Array of Integers 
C Program to Implement BogoSort in an Integer Array 
C Program to Perform Shell Sort without using Recursion

 

1. C Examples on Basic Sorting Algorithms

 

 

C Program to Sort N Numbers in Ascending Order using Bubble Sort

 

This C Program sorts the numbers in ascending order using bubble sort. Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. Here we need to sort a number in ascending order.

Here is source code of the C program to sort the numbers in ascending order using bubble sort. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C program to sort N numbers in ascending order using Bubble sort
  3.  * and print both the given and the sorted array
  4.  */
  5. #include <stdio.h>
  6. #define MAXSIZE 10
  7.  
  8. void main()
  9. {
  10.     int array[MAXSIZE];
  11.     int i, j, num, temp;
  12.  
  13.     printf("Enter the value of num \n");
  14.     scanf("%d", &num);
  15.     printf("Enter the elements one by one \n");
  16.     for (i = 0; i < num; i++)
  17.     {
  18.         scanf("%d", &array[i]);
  19.     }
  20.     printf("Input array is \n");
  21.     for (i = 0; i < num; i++)
  22.     {
  23.         printf("%d\n", array[i]);
  24.     }
  25.     /*   Bubble sorting begins */
  26.     for (i = 0; i < num; i++)
  27.     {
  28.         for (j = 0; j < (num - i - 1); j++)
  29.         {
  30.             if (array[j] > array[j + 1])
  31.             {
  32.                 temp = array[j];
  33.                 array[j] = array[j + 1];
  34.                 array[j + 1] = temp;
  35.             }
  36.         }
  37.     }
  38.     printf("Sorted array is...\n");
  39.     for (i = 0; i < num; i++)
  40.     {
  41.         printf("%d\n", array[i]);
  42.     }
  43. }

 

 
$ cc pgm21.c
$ a.out
Enter the value of num
6
Enter the elements one by one
23
45
67
89
12
34
Input array is
23
45
67
89
12
34
Sorted array is...
12
23
34
45
67
89


This is a C Program to sort an array in ascending order.

Problem Description

This program will implement a one-dimentional array of some fixed size, filled with some random numbers, then will sort all the filled elements of the array.

Problem Solution

1. Create an array of fixed size (maximum capacity), lets say 10.
2. Take n, a variable which stores the number of elements of the array, less than maximum capacity of array.
3. Iterate via for loop to take array elements as input, and print them.
4. The array elements are in unsorted fashion, to sort them, make a nested loop.
5. In the nested loop, the each element will be compared to all the elements below it.
6. In case the element is greater than the element present below it, then they are interchanged
7. After executing the nested loop, we will obtain an array in ascending order arranged elements.

Program/Source Code

Here is source code of the C program to sort the array in an ascending order. The program is successfully compiled and tested using Turbo C compiler in windows environment. The program output is also shown below.

  1.  
  2.     /*
  3.      * C program to accept N numbers and arrange them in an ascending order
  4.      */
  5.  
  6.     #include <stdio.h>
  7.     void main()
  8.     {
  9.  
  10.         int i, j, a, n, number[30];
  11.         printf("Enter the value of N \n");
  12.         scanf("%d", &n);
  13.  
  14.         printf("Enter the numbers \n");
  15.         for (i = 0; i < n; ++i)
  16.             scanf("%d", &number[i]);
  17.  
  18.         for (i = 0; i < n; ++i) 
  19.         {
  20.  
  21.             for (j = i + 1; j < n; ++j)
  22.             {
  23.  
  24.                 if (number[i] > number[j]) 
  25.                 {
  26.  
  27.                     a =  number[i];
  28.                     number[i] = number[j];
  29.                     number[j] = a;
  30.  
  31.                 }
  32.  
  33.             }
  34.  
  35.         }
  36.  
  37.         printf("The numbers arranged in ascending order are given below \n");
  38.         for (i = 0; i < n; ++i)
  39.             printf("%d\n", number[i]);
  40.  
  41.     }
Program Explanation

1. Declare an array of some fixed capacity, lets say 30.
2. From users, take a number N as input, which will indicate the number of elements in the array (N <= maximum capacity)
3. Iterating through for loops (from [0 to N) ), take integers as input from user and print them. These input are the elements of the array.
4. Now, create a nested for loop with i and j as iterators.
5. Start the sorting in ascending order by extracting each element at position i of outer loop.
6. This element is being compared to every element from position i+1 to size-1 (means all elements present below this extracted element)
7. In case any of the extracted element is greater than the element below it, then these two interchange their position, else the loop continues.
8. After this nested loop gets executed, we get all the elements of the array sorted in ascending order.

Runtime Test Cases
 
Enter the value of N
6
Enter the numbers
3
78
90
456
780
200
The numbers arranged in ascending order are given below
3
78
90
200
456
780


This is a C Program to sort the names in an alphabetical order.

Problem Description

The program will accept some names from the user as input & then sorts them in an alphabetical order using string operation.

Problem Solution

1. Create a 2D character array to store names of some fixed size.
2. Take names as input from users using for loop.
3. Now, sort this array of names using Selection sort.
4. Make a nested for loop, where the upper loop extracts each name and inner loop compares this name by the rest of the names below it.
5. After executing both the loops, rearranging all the names, finally an array of alphabetically sorted array will be obtained.

Program/Source Code

Here is source code of the C program to sort the names in an alphabetical order. The program is successfully compiled and tested using Turbo C compiler in windows environment. The program output is also shown below.

  1.     /*
  2.      * C program to read N names, store them in the form of an array
  3.      * and sort them in alphabetical order. Output the given names and
  4.      * the sorted names in two columns side by side.
  5.      */
  6.  
  7.     #include <stdio.h>
  8.     #include <string.h>
  9.     void main()
  10.     {
  11.  
  12.         char name[10][8], tname[10][8], temp[8];
  13.         int i, j, n;
  14.  
  15.         printf("Enter the value of n \n");
  16.         scanf("%d", &n);
  17.         printf("Enter %d names n \n", n);
  18.  
  19.         for (i = 0; i < n; i++) 
  20.         {
  21.             scanf("%s", name[i]);
  22.             strcpy(tname[i], name[i]);
  23.         }
  24.  
  25.         for (i = 0; i < n - 1 ; i++)
  26.         {
  27.             for (j = i + 1; j < n; j++)
  28.             {
  29.                 if (strcmp(name[i], name[j]) > 0) 
  30.                 {
  31.                     strcpy(temp, name[i]);
  32.                     strcpy(name[i], name[j]);
  33.                     strcpy(name[j], temp);
  34.                 }
  35.             }
  36.         }
  37.  
  38.         printf("\n----------------------------------------\n");
  39.         printf("Input NamestSorted names\n");
  40.         printf("------------------------------------------\n");
  41.  
  42.         for (i = 0; i < n; i++) 
  43.         {
  44.             printf("%s\t\t%s\n", tname[i], name[i]);
  45.         }
  46.  
  47.         printf("------------------------------------------\n");
  48.  
  49.     }
Program Explanation

1. Create two 2D character array of some fixed capacity.
2. Take the size of the array as input from the user, and fill the array with names taking them as input.
3. Now to sort this array, first make a nested for loop with i and j as iterators respectively.
4. The outer will will run from 0 to size – 1 , extracting each name of position i, one by one.
5. The inner loop will run from i+1 to size-1, comparing the name extracted by outer loop to all the names below it.
6. At each comparison, if the name above is alphabetically greater than the name below, then these two names are interchanged.
7. After executing the nested loop code section, we will obtain an array of names in proper alphabetical order.

Runtime Test Cases
Enter the value of n
7
Enter 7 names
heap
stack
queue
object
class
program
project
 
----------------------------------------
Input Names    Sorted names
------------------------------------------
heap           class
stack          heap
queue          object
object         program
class          project
program        queue
project        stack
------------------------------------------

C Program to Implement Selection Sort Recursively

This C Program implements a Selection sort. Selection sort works by finding the smallest unsorted item in the list and swapping it with the item in the current position. It is used for sorting unsorted list of elements.

 

Here is the source code of the C program to display a linked list in reverse. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C Program to Implement Selection Sort Recursively
  3.  */
  4. #include <stdio.h>
  5.  
  6. void selection(int [], int, int, int, int);
  7.  
  8. int main()
  9. {
  10.     int list[30], size, temp, i, j;
  11.  
  12.     printf("Enter the size of the list: ");
  13.     scanf("%d", &size);
  14.     printf("Enter the elements in list:\n");
  15.     for (i = 0; i < size; i++)
  16.     {
  17.         scanf("%d", &list[i]);
  18.     }
  19.     selection(list, 0, 0, size, 1);
  20.     printf("The sorted list in ascending order is\n");
  21.     for (i = 0; i < size; i++)
  22.     {
  23.         printf("%d  ", list[i]);
  24.     }
  25.  
  26.     return 0;
  27. }
  28.  
  29. void selection(int list[], int i, int j, int size, int flag)
  30. {
  31.     int temp;
  32.  
  33.     if (i < size - 1)
  34.     {
  35.         if (flag)
  36.         {
  37.             j = i + 1;
  38.         }
  39.         if (j < size)
  40.         {
  41.             if (list[i] > list[j])
  42.             {
  43.                 temp = list[i];
  44.                 list[i] = list[j];
  45.                 list[j] = temp;
  46.             }
  47.             selection(list, i, j + 1, size, 0);
  48.         }
  49.         selection(list, i + 1, 0, size, 1);
  50.     }
  51. }

 

$ cc pgm18.c
$ a.out
Enter the size of the list: 5
Enter the elements in list:
23
45
64
12
34
The sorted list in ascending order is
12  23  34  45  64



C Program to Implement Selection Sort Method using Functions



This C Program implements selection sort method using functions. Selection sort is among the simplest of sorting techniques. It works as follows: first find the smallest in the array and exchange it with the element in the first position, then find the second smallest element and exchange it with the element in the second position, and continue in this way until the entire array is sorted.

 

Here is source code of the C program to implement selection sort method using functions. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C program for SELECTION sort which uses following functions
  3.  * a) To find maximum of elements
  4.  * b) To swap two elements
  5.  */
  6. #include <stdio.h>
  7.  
  8. int findmax(int b[10], int k);
  9. void exchang(int b[10], int k);
  10. void main()
  11. {
  12.     int array[10];
  13.     int i, j, n, temp;
  14.  
  15.     printf("Enter the value of n \n");
  16.     scanf("%d", &n);
  17.     printf("Enter the elements one by one \n");
  18.     for (i = 0; i < n; i++)
  19.     {
  20.         scanf("%d", &array[i]);
  21.     }
  22.     printf("Input array elements \n");
  23.     for (i = 0; i < n ; i++)
  24.     {
  25.         printf("%d\n", array[i]);
  26.     }
  27.     /*  Selection sorting begins */
  28.     exchang(array, n);
  29.     printf("Sorted array is...\n");
  30.     for (i = 0; i < n; i++)
  31.     {
  32.         printf("%d\n", array[i]);
  33.     }
  34. }
  35. /*  function to find the maximum value */
  36. int findmax(int b[10], int k)
  37. {
  38.     int max = 0, j;
  39.     for (j = 1; j <= k; j++)
  40.     {
  41.         if (b[j] > b[max])
  42.         {
  43.             max = j;
  44.         }
  45.     }
  46.     return(max);
  47. }
  48. void exchang(int b[10], int k)
  49. {
  50.     int  temp, big, j;
  51.     for (j = k - 1; j >= 1; j--)
  52.     {
  53.         big = findmax(b, j);
  54.         temp = b[big];
  55.         b[big] = b[j];
  56.         b[j] = temp;
  57.     }
  58.     return;
  59. }

 

$ cc pgm33.c
$ a.out
Enter the value of n
4
Enter the elements one by one
57
90
34
78
Input array elements
57
90
34
78
Sorted array is...
34
57
78
90





C Program to Input Few Numbers & Perform Merge Sort on them using Recursion



The following C program, using recursion, performs merge sort. A merge sort is a sorting algorithm with complexity of O(nlogn). It is used for sorting numbers, structure, files.

 

Here is the source code of the C program to display a linked list in reverse. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C Program to Input Few Numbers & Perform Merge Sort on them using Recursion
  3.  */
  4.  
  5. #include <stdio.h>
  6.  
  7. void mergeSort(int [], int, int, int);
  8. void partition(int [],int, int);
  9.  
  10. int main()
  11. {
  12.     int list[50];
  13.     int i, size;
  14.  
  15.     printf("Enter total number of elements:");
  16.     scanf("%d", &size);
  17.     printf("Enter the elements:\n");
  18.     for(i = 0; i < size; i++)
  19.     {
  20.          scanf("%d", &list[i]);
  21.     }
  22.     partition(list, 0, size - 1);
  23.     printf("After merge sort:\n");
  24.     for(i = 0;i < size; i++)
  25.     {
  26.          printf("%d   ",list[i]);
  27.     }
  28.  
  29.    return 0;
  30. }
  31.  
  32. void partition(int list[],int low,int high)
  33. {
  34.     int mid;
  35.  
  36.     if(low < high)
  37.     {
  38.         mid = (low + high) / 2;
  39.         partition(list, low, mid);
  40.         partition(list, mid + 1, high);
  41.         mergeSort(list, low, mid, high);
  42.     }
  43. }
  44.  
  45. void mergeSort(int list[],int low,int mid,int high)
  46. {
  47.     int i, mi, k, lo, temp[50];
  48.  
  49.     lo = low;
  50.     i = low;
  51.     mi = mid + 1;
  52.     while ((lo <= mid) && (mi <= high))
  53.     {
  54.         if (list[lo] <= list[mi])
  55.         {
  56.             temp[i] = list[lo];
  57.             lo++;
  58.         }
  59.         else
  60.         {
  61.             temp[i] = list[mi];
  62.             mi++;
  63.         }
  64.         i++;
  65.     }
  66.     if (lo > mid)
  67.     {
  68.         for (k = mi; k <= high; k++)
  69.         {
  70.             temp[i] = list[k];
  71.             i++;
  72.         }
  73.     }
  74.     else
  75.     {
  76.         for (k = lo; k <= mid; k++)
  77.         {
  78.              temp[i] = list[k];
  79.              i++;
  80.         }
  81.     }
  82.  
  83.     for (k = low; k <= high; k++)
  84.     {
  85.         list[k] = temp[k];
  86.     }
  87. }

 

$ cc pgm28.c
$ a.out
Enter total number of elements:5
Enter the elements:
12
36
22
76
54
After merge sort:
12   22   36   54   76





C Program to Perform Quick Sort on a set of Entries from a File using Recursion


The following C program, using recursion, performs quick sort. A quick sort is a sorting algorithm with complexity of O(nlogn). It is used for sorting numbers, structure, files.

 

Here is the source code of the C program to display a linked list in reverse. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2. * C Program to Perform Quick Sort on a set of Entries from a File 
  3. * using Recursion
  4. */
  5. #include <stdio.h>
  6.  
  7. void quicksort (int [], int, int);
  8.  
  9. int main()
  10. {
  11.     int list[50];
  12.     int size, i;
  13.  
  14.     printf("Enter the number of elements: ");
  15.     scanf("%d", &size); 
  16.     printf("Enter the elements to be sorted:\n");
  17.     for (i = 0; i < size; i++)
  18.     {
  19.         scanf("%d", &list[i]);
  20.     } 
  21.     quicksort(list, 0, size - 1);
  22.     printf("After applying quick sort\n");
  23.     for (i = 0; i < size; i++)
  24.     {
  25.         printf("%d ", list[i]);
  26.     }
  27.     printf("\n");
  28.  
  29.     return 0;
  30. }
  31. void quicksort(int list[], int low, int high)
  32. {
  33.     int pivot, i, j, temp;
  34.     if (low < high)
  35.     {
  36.         pivot = low;
  37.         i = low;
  38.         j = high;
  39.         while (i < j) 
  40.         {
  41.             while (list[i] <= list[pivot] && i <= high)
  42.             {
  43.                 i++;
  44.             }
  45.             while (list[j] > list[pivot] && j >= low)
  46.             {
  47.                 j--;
  48.             }
  49.             if (i < j)
  50.             {
  51.                 temp = list[i];
  52.                 list[i] = list[j];
  53.                 list[j] = temp;
  54.             }
  55.         }
  56.         temp = list[j];
  57.         list[j] = list[pivot];
  58.         list[pivot] = temp;
  59.         quicksort(list, low, j - 1);
  60.         quicksort(list, j + 1, high);
  61.     }
  62. }

 

$ cc pgm29.c
$ a.out
Enter the number of elements: 6
Enter the elements to be sorted:
67
45
24
98
12
38
After applying quick sort
12 24 38 45 67 98


2. C Examples on Searching Algorithms


C Program to Read an Array and Search for an Element

 

This is a C Program to read an array and search for an element.

Problem Description

This program will implement a one-dimentional array, take a number form users to search for in the array using Binary Search.

Problem Solution

1. Create an array of some certain size and define its elements in sorted fashion.
2. Now take an input from the users which you want to search for.
3. Take two variables pointing to the first and last index of the array (namely low and high)
4. Run start a while and run it until low equals high.
5. Now, take a mid of low and high value, check whether value at mid equals the user input.
6. In case it matches the user input, it means we found the number, after which we must break out from the loop.
7. And if user input is greater than value at mid, then low is assigned the value of mid. Similarly if user input is smaller than value at mid, then high is assigned the value of mid.
8. In this way, the region of finding the user input becomes half.

Program/Source Code

Here is source code of the C program to read an array and search for an element. The program is successfully compiled and tested using Turbo C compiler in windows environment. The program output is also shown below.


  1.     /*
  2.      * C program accept an array of N elements and a key to search.
  3.      * If the search is successful, it displays "SUCCESSFUL SEARCH".
  4.      * Otherwise, a message "UNSUCCESSFUL SEARCH" is displayed.
  5.      */

  6.     #include <stdio.h>
  7.     void main()
  8.     {
  9.         int array[20];
  10.         int i, low, mid, high, key, size;
  11.         printf("Enter the size of an array\n");
  12.         scanf("%d", &size); 
  13.         printf("Enter the array elements\n");
  14.         for (i = 0; i < size; i++) 
  15.          {
  16.             scanf("%d", &array[i]);
  17.           }
  18.         printf("Enter the key\n");
  19.         scanf("%d", &key);
  20.         /*  search begins */
  21.         low = 0;
  22.         high = (size - 1);
  23.         while (low <= high) 
  24.         {
  25.             mid = (low + high) / 2;
  26.              if (key == array[mid]) 
  27.             {
  28.                 printf("SUCCESSFUL SEARCH\n");
  29.                 return;
  30.             }
  31.              if (key < array[mid])
  32.                 high = mid - 1;
  33.             else
  34.                 low = mid + 1;
  35.          }
  36.         printf("UNSUCCESSFUL SEARCH\n");
  37.     }
Program Explanation

1. Declare an array of capacity 20, taking size from users, define all the element of the array but in sorted fashion.
2. Now, take three variables, low pointing to the first index of array i.e 0, last index of array i.e size-1, and mid.
3. Run a loop till the low become equal to high.
4. Inside this loop, first calculate mid using (high + low) / 2 = mid.
5. Check if the value at mid matches the user input, if it does, that means we found the element and now we can return by breaking out from the loop.
6. If user input is greater than value at mid, then low is shifted to mid, similarly if user input is smaller than mid, then high id shifted to mid.
7. In this way, each time, we halved the region where we are finding the element.

Runtime Test Cases
Enter the size of an array
4
Enter the array elements
90
560
300
390
Enter the key
90
SUCCESSFUL SEARCH
 
$ a.out
Enter the size of an array
4
Enter the array elements
100
500
580
470
Enter the key
300
UNSUCCESSFUL SEARCH

C Program to accept Sorted Array and do Search using Binary Search

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.

Problem Solution

1. We will be having an array of numbers, we just need to find out whether the element is present in the array or not.
2. It can be done using Linear Search but it takes up a lot of time, so we need a better searching algorithm that performs the same task but in less time in comparison to Linear Search.
3. In worst case Linear Search takes O(n) time, but Binary Search takes O(log n) time in worst case.

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".

Worst case time complexity: O(log n).

Program/Source Code

Here is source code of the C Program to find whether the element is present in the array or not using Binary Search Algorithm. The program is successfully compiled and tested using Codeblocks gnu/gcc compiler on Windows 10. The program output is also shown below.

  1.  

  2. /*

  3.  * C program to accept N numbers sorted in ascending order

  4.  * and to search for a given number using Binary Search.

  5.  * Report success or failure.

  6.  */

  7. #include <stdio.h>

  8. void main()
  9. {
  10. int array[10];
  11. int i, j, num, temp, keynum;
  12. int low, mid, high;
  13. printf("Enter the value of num \n");
  14. scanf("%d", &num);
  15. printf("Enter the elements one by one \n");
  16. for (i = 0; i < num; i++)
  17. {
  18. scanf("%d", &array[i]);
  19. }
  20. printf("Input array elements \n");
  21. for (i = 0; i < num; i++)
  22. {
  23. printf("%d\n", array[i]);
  24. }
  25. /* Bubble sorting begins */

  26. for (i = 0; i < num; i++)

  27. {

  28. for (j = 0; j < (num - i - 1); j++)

  29. {

  30. if (array[j] > array[j + 1])

  31. {

  32. temp = array[j];

  33. array[j] = array[j + 1];

  34. array[j + 1] = temp;

  35. }

  36. }

  37. }

  38. printf("Sorted array is...\n");

  39. for (i = 0; i < num; i++)

  40. {

  41. printf("%d\n", array[i]);

  42. }

  43. printf("Enter the element to be searched \n");

  44. scanf("%d", &keynum);

  45. /* Binary searching begins */

  46. low = 1;

  47. high = num;

  48. do

  49. {

  50. mid = (low + high) / 2;

  51. if (keynum < array[mid])

  52. high = mid - 1;

  53. else if (keynum > array[mid])

  54. low = mid + 1;

  55. } while (keynum != array[mid] && low <= high);

  56. if (keynum == array[mid])
  57. {
  58. printf("SEARCH SUCCESSFUL \n");
  59. }
  60. else
  61. {
  62. printf("SEARCH FAILED \n");
  63. }
  64. }

Program Explanation

1. A Binary Search is a quick and efficient method of finding a specific target value from a set of ordered items. A Binary search is also known as a half-interval search.
2. Here in this program, the element to be searched is denoted by keynum.
3. In order to apply Binary Search, we need to have a sorted array. In the above program, we have used Bubble Sort before applying Binary Search.
4. After sorting the elements in ascending order, we have applied a binary search by first comparing the keynum with the middle element of the array.
5. If the value of keynum is equal to the middle element of the array, we have simply printed “SEARCH SUCCESSFUL”.
6. If keynum is other than the middle element of the array, we divide the array into two parts one having all the elements less than the middle element and the other having all the elements greater than the middle element, and start locating for keynum in the desired part.
7. If keynum is greater than the middle element, the value of low (starting index of the array), will become mid+1 and if it is less than the middle element high (last index of the array), will become mid-1. “mid” is the middle index of the array.
8. When we are modifying the values of low and high, we are basically dividing the array into two halves, and then looking for keynum in respective half.
9. The Best case time complexity of Binary Search is O(1). The only condition for implementing Binary Search is that the array should be sorted.

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