BINARY SEARCH

• Problem Description

  
  Develop a program to implement the binary search algorithm. This technique compares the search key value of the element that is midway in a sorted lies. Then ;
  (a) If they match, the search is over.
  (b) If the search key value is less than the middle value, then the first half of list contains the key value. 
  (c) If the search key value is greater than the middle value, then the second half contains the key value.
  Repeat this divide and-conquer strategy until we have match. If the list is reduced to one non-matching element, then the list does not contain the key value.
  

• CODING ARENA::

• #include <stdio.h>

   

  int main()

  {

     int c, first, last, middle, n, search, array[10000];

     scanf("%d",&n);

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

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

     scanf("%d", &search);

    first = 0;

    last = n - 1;

    middle = (first+last)/2;

    while (first <= last) {

        if (array[middle] < search)

           first = middle + 1;    

        else if (array[middle] == search) {

           printf("%d found at location %d\n", search, middle+1);

           break;

        }

        else

           last = middle - 1;

   

        middle = (first + last)/2;

     }

     if (first > last)

        printf("%d is not present in the list\n",search);

    return 0;

  }

• Test Case 1

  
  Input (stdin)

  13
  
  10 11 12 13 1 3 2 4 7 8 110 122 123
  
  2
  
  

  Expected Output

  2 found at location 7

• Test Case 2

  
  Input (stdin)

  10
  
  1000 1234 2345 3500 1222 7899 8900 6666 7777 1111
  
  9999
  
  

  Expected Output

  9999 is not present in the list