Binary Search and it's implementation

 What is Binary Search?

The binary search technique takes O(log n) time to discover a particular element in a list of elements, where n is the total number of elements in the list. Only a sorted list of elements can be used with the binary search method. That is, the binary search is only utilized with a list of components that has already been organised in a specific order. A list of elements arranged in random order cannot be searched using the binary search. This search begins by comparing the search element to the list's middle element. If both are found to be identical, the outcome is "element discovered."

Steps to search an element using Binary Search:

Binary search is implemented using following steps:

Step 1)  Read the elements in an array in ascending order.

Step 2 ) Read the search element from the user.

Step 3)  Find the middle element in the sorted list.

Step 4)  Compare the search element with the middle element in the sorted list.

Step 5)  If both are matched, then display "Given element is found!!!" and terminate the function.

Step 6)  If both are not matched, then check whether the search element is smaller or larger than the middle element.

Step 7)  If the search element is smaller than middle element, repeat steps 2, 3, 4 and 5 for the left sub list of the middle element.

Step 8)  If the search element is larger than middle element, repeat steps 2, 3, 4 and 5 for the right sub list of the middle element.

Step 9)  Repeat the same process until we find the search element in the list or until sub list contains only one element.

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

Step by Step Example of Binary Search:

Binary Search Algorithm:

BINARY_SEARCH(A, lower_bound, upper_bound, VAL)

• Step 1: [INITIALIZE] SET BEG = lower_bound
  END = upper_bound, POS = - 1
• Step 2: Repeat Steps 3 and 4 while BEG <=END
• Step 3: SET MID = (BEG + END)/2
• Step 4: IF A[MID] = VAL
  SET POS = MID
  PRINT POS
  Go to Step 6
  ELSE IF A[MID] > VAL
  SET END = MID - 1
  ELSE
  SET BEG = MID + 1
  [END OF IF]
  [END OF LOOP]
• Step 5: IF POS = -1
  PRINT "VALUE IS NOT PRESENT IN THE ARRAY"
  [END OF IF]
• Step 6: EXIT

Implementation of Binary Search in C:

// WAP in C to perform binary search to search any target element

#include <stdio.h>

int main()

{

int i, low, high, mid, n, key, array[100];

printf("\n\t Enter number of elements:");

scanf("%d",&n);

printf("\n\tEnter %d integers in ascending order:", n);

for(i = 0; i < n; i++)  // Read the elements of the array

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

printf("\n\t Enter value to find:");

scanf("%d", &key);

low = 0;

high = n - 1;

mid = (low+high)/2;

while (low <= high)

{

   if(array[mid] < key)

      low = mid + 1;

   else if (array[mid] == key) 

   {

      printf("%d found at location %d.n", key, mid+1);

      break;

    }

   else

      high = mid - 1;

  mid = (low + high)/2;

}

if(low > high)

     printf("Not found! %d isn't present in the list.n", key);

return 0;

}