Search a word using binary search technique - C Program

Write a C program to search a word using binary search technique.

Solution:

Binary Search:
Binary search works on the sorted array elements. In binary search we divide the search interval in half and then find the target value within the sorted array.

In this example we compare the target element with middle element. If it matches, return the middle element otherwise divide the array in two parts.

Program

#include <stdio.h>                     //standard input output functions
#include<string.h>                      //console functions
#define max 20                             //define max as 20
void search(char [][20],int,char[]);        //search function
void main()                  //main function
{
    char string[max][20],t[20],word[20];        //variables
    int i, j, n;
    printf("Enter the number of words: \n");
    scanf("%d", &n);                             //getting number of words
    printf("Enter the words: \n");
    for (i = 0; i < n; i++)                   //entering words
            scanf("%s",string[i]);
    printf("Input words \n");                    //displaying the words
    for (i = 0; i < n; i++)
         printf("%s\n", string[i]);

    /*  sorting elements as for binary search elements should be sorted */
    for (i = 1; i < n; i++)
    {
      for (j = 1; j < n; j++)
      {                                              //if the previous string is greater than next
          if (strcmp(string[j - 1], string[j]) > 0)
          {                                         //swap their positions
              strcpy(t, string[j - 1]);
               strcpy(string[j - 1], string[j]);
              strcpy(string[j], t);
          }
      }
   }
   printf("Enter the element to be searched: \n");
   scanf("%s",word);                                   //entering the word to be searched
   search(string,n,word);                          //calling search function
}

/*  Binary searching begins */
void search(char string[][20],int n,char word[])
{
    int lb, mid, ub;
    lb = 0;                             //lower bound to 0
    ub = n;                             //upper bound to n
    do
    {
        mid = (lb + ub) / 2;             //finding the mid of the array
        if ((strcmp(word,string[mid]))<0)       //compare the word with mid
            ub = mid - 1;                          //if small then decrement ub
        else if ((strcmp(word,string[mid]))>0)
            lb = mid + 1;                          //if greater then increment lb
     /*repeat the process till lb doesn't becomes ub and string is found */   
    } while ((strcmp(word,string[mid])!=0) && lb <= ub);
    if ((strcmp(word,string[mid]))==0)              //if string is found
          printf("SEARCH SUCCESSFUL \n");
    else                                        //if not found
          printf("SEARCH FAILED \n");
}


Output:

binary search technique
▲