Binary Search–Iterative and Recursive

In a sorted list, its straight forward to search for a number. Just check whether the number is less or greater than the median of the list. If its less, avoid the second half, greater, the first half. continue until you get the position of the number. Such a division in the search domain yields faster search results.

Metaphor

   Do you remember playing the game "Guess a Number", where the responses to the statement "I am thinking of a number between 1 and 100" are "Too High", "Too Low", or "You Got It!"?  A strategy that is often used when playing this game is to divide the intervals between the guess and the ends of the range in half.  This strategy helps you to quickly narrow in on the desired number. [Source: http://mathbits.com/mathbits/compsci/arrays/Binary.htm]

  This is the base of the binary search. Some conditions are verified over a sorted list such us “Greater than” and “Lesser than” to reduce the probability of getting the searched for element inside a particular smaller list. This is a kind of divide and conquer methodology.

Concept

  Take a sorted list and keep on splitting it until the number required to be found on the list is not found. The splitting is based on greater/lesser condition. If the number is greater, the start position moves to the right side and if it is lesser, the end position moves towards the left.

Code

   1:  int binary_search(int *arr, int query, int size)

   2:  {

   3:      int start = 0;

   4:      int end = size;

   5:      int found =0;

   6:      while(found == 0)

   7:      {

   8:          int mid = (int) floor(((float)start + (float)end)/2);

   9:          if (arr[mid] == query)

  10:          {

  11:              found = mid;

  12:              continue;

  13:          }

  14:          else if(query > arr[mid])

  15:          {

  16:              start = mid+1;

  17:          }

  18:          else

  19:          {

  20:              end = mid-1;

  21:          }

  22:   

  23:      }

  24:      return found;

  25:  }

  26:   

  27:  int b_search(int *arr, int start, int end, int query)

  28:  {

  29:      int mid = (int) floor(((float)start + (float)end )/2);

  30:      if(arr[mid] == query)

  31:          return mid;

  32:      else if(query > arr[mid])

  33:          return b_search(arr, mid+1, end, query);

  34:      else

  35:          return b_search(arr, start, mid-1, query);

  36:  }

  37:  void main()

  38:  {

  39:      int A[] = {10,15,24,36,45,55,64,73,90,98};

  40:      int pos = binary_search(A, 64, 9);

  41:      int pos1 = b_search(A, 0, 9, 64);

  42:  }

Important points

• This is a divide and conquer approach. It can be represented either using iteration or using recursion.
• The movement of start and end should be noted clearly. When query is greater, start moved to mid and when it is lesser, end moves to mid.
• While start moves +1, since mid is already checked for, end moves in –1 for the same reason.
• The recursive version is almost ditto. Only that some temporaries are removed and a while loop is gone.