Binary Search

Binary Search

Procedure:

Step 1: Read the search element from the user

Step 2: Find the middle element in the sorted list

Step 3: Compare, the search element with the middle element in the sorted list.

Step 4: If both are matching, then display "Given element found!!!" and terminate the function

Step 5: If both are not matching, then check whether the search element is smaller or larger than middle element.

Step 6: If the search element is smaller than middle element, then repeat steps 2, 3, 4 and 5 for the left sublist of the middle element.

Step 7: If the search element is larger than middle element, then repeat steps 2, 3, 4 and 5 for the right sub-list of the middle element.

Step 8: Repeat the same process until we find the search element in the list or until sublist contains only one element.

Step 9: If that element also doesn't match with the search elmement, then display "Element not found in the list!!!" and terminate the function.

Example:

Program:

#include<stdio.h>

#include<conio.h>

void main()

{

   int first, last, middle, n, i, target,
a[100];

clrscr();

   printf("Enter the size of the list:
");

scanf("%d", &n);

   printf("Enter %d integer values in
Ascending order \n", n);

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

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

   printf("Enter value to be search:
");

scanf("%d", &target);

first = 0;

last = n - 1;

middle = (first+last)/2;

while (first <= last)

{

if (a[middle] < target)

             first = middle +
1;

else if (a[middle] = = target)

{

             printf("Element
found at index %d.\n", middle);

break;

}

else

last = middle - 1;

middle = (first + last)/2;

}

if (first > last)

      printf("Element Not found in the
list.");

getch();

}

DS