C Program to perform binary search to find a number

What is a binary search algorithm?

In this c program, we are implementing a binary search algorithm to search for a key number. The binary search algorithm is also called the "half interval algorithm" or "logarithmic algorithm". to implement the binary search algorithm, we need to sort the array in ascending or descending order.

The algorithm compares the central element of the array with the keyword. If we find the element, its position will be returned with the message search element found. Else algorithm repeats the same step on the left sub array if the middle number is less than the keyword else if it will search the right sub array if the element is greater than the central element of the array.

Note: The Worst-case Complexity of the Binary Search is O(log n).

What is the Bubble sort technique? How binary search implemented in C?

After importing the header files and initializing the variable, we accept user input into array and sort the array using the bubble sorting technique. (please refer to the "bubble sort" in the previous program). After sorting the elements in ascending order, we display the sorted array and start the binary search using a 'do while' loop. Inside the loop, take the central element of the array and compare it with the key until we find the element.

ALGORITHM

STEP 1: Include the Header files into the C program to use the built-in functions.

STEP 2:  Initialize the Variables and Declare them using C programming syntax.

STEP 3: Accept the number of terms from the user using printf and scanf built-in functions.

STEP 4: Accept the elements into the Array using 'for loop' and scanf.

STEP 5: Display the elements of the Array using 'for loop' and printf.

STEP 6: Open the nested 'for loop' for implementing the Bubble Sort Algorithm.

STEP 7: Using an if condition check, the comparing element is greater than the compared element

STEP 8: If so, swap the elements using the temporary variable.

STEP 9: Print the sorted Array using 'for loop' and printf.

STEP 10: Accept the element to be searched from the user using printf and scanf.

STEP 11: Assign the Low as one and High as the number of terms.

STEP 12: Open a 'do while' with condition ( keynum!=array[mid] && low <= high) until the condition get satisfied. keynum = searching element.

STEP 13: Calculate the middle element using the formula (low + high) / 2.

STEP 14: Using an 'if' condition check, the Keynum is less than Array middle element. If so, high =mid -1.

STEP 15: Else check the keynum is less than Array middle element if so low = mid + 1.

STEP 16: Check using an 'if' condition that keynum is equal to the Array middle element. If so, print the Search is successful.

STEP 17: else print that the Search is failed and quit the C program.

C Source Code

                                          #include <stdio.h>
#include <conio.h>

void main()
{

  int array[10];
  int i, j, N, temp, keynum;
  int low, mid, high;
  clrscr();
  printf("Enter the value of N\n"); /* gets the value of elements one by one  */
  scanf("%d", & N);
  printf("Enter the elements one by one\n");
  for (i = 0; i < N; i++) {
    printf("%d\n", array[i]);
  }

  /* Bubble sorting begins */

  for (i = 0; i < N; i++) {
    for (j = 0; j < (N - i - 1); j++) {
      if (array[j] > array[j + 1]) /* sorting the array using bubble sort  */ {
        temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
  printf("Sorted array is...\n"); /* displays the sorted array */
  for (i = 0; i < array[mid])
    high = mid - 1;
  else if (keynum > array[mid])
    low = mid + 1;
}
while (keynum != array[mid] && low <= high); /* End of do- while */
if (keynum == array[mid]) {
  printf("SUCCESSFUL SEARCH\n");
} else {
  printf("Search is FAILED\n"); /* displays search success or failure */
}
} /* End of main*/
                                      

OUTPUT

Enter the value of N
4

Enter the elements one by one
3
1
4
2

Input array elements
3
1
4
2

Sorted array is...
1
2
3
4

Enter the element to be searched
4

SUCCESSFUL SEARCH