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.






    /*


     * C program accept an array of N elements and a key to search.


     * If the search is successful, it displays "SUCCESSFUL SEARCH".


     * Otherwise, a message "UNSUCCESSFUL SEARCH" is displayed.


     */






    #include <stdio.h>


    void main()


    {


        int array[20];


        int i, low, mid, high, key, size;


        printf("Enter the size of an array\n");


        scanf("%d", &size); 


        printf("Enter the array elements\n");


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


         {


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


          }


        printf("Enter the key\n");


        scanf("%d", &key);


        /*  search begins */


        low = 0;


        high = (size - 1);


        while (low <= high) 


        {


            mid = (low + high) / 2;


             if (key == array[mid]) 


            {


                printf("SUCCESSFUL SEARCH\n");


                return;


            }


             if (key < array[mid])


                high = mid - 1;


            else


                low = mid + 1;


         }


        printf("UNSUCCESSFUL SEARCH\n");


    }








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.








 


/*


 * 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 <stdio.h>

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");
 }

}








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