/*
 * bin_srch.c
 * This program generates a sorted array of integers and lets the user query
 * for numbers. It uses binary search to answer the queries efficiently.
 */

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

/* Prototypes: */
int bin_search (const int *arr, int n, int q);

int main ()
{
  int       array[MAX_SIZE];
  const int max_step = 10;
  int       step;
  int       curr;
  int       i;

  /* Fill the array with randomal ascending numbers. */
  array[0] = 1;

  srand (time (NULL));
  for (i = 1; i < MAX_SIZE; i++)
  {
    /* Pick a step size between 1 and max_step. */
    step = 1 + (int)(max_step * (float)rand() / (RAND_MAX + 1.0));

    array[i] = array[i - 1] + step;
  }

  /* Print out the array. */
  for (i = 0; i < MAX_SIZE; i++)
    printf ("%d ", array[i]);
  printf ("\n");

  /* Answer the user's queries. */
  while (1)
  {
    /* Read the next number. */
    printf ("Please enter a number (or < 0 to stop): ");
    scanf ("%d", &curr);

    if (curr <= 0)
      break;

    /* Search for it and print the result. */
    i = bin_search (array, MAX_SIZE, curr);

    if (i < 0)
      printf (" (%d) is not found in the array.\n", curr);
    else
      printf (" (%d) is found in index %d of the array.\n", curr, i);
  }

  return (0);
}

/* ------------------------------------------------------------------------
 * Function: bin_search
 * Purpose : Perform binary search to locate a query in a sorted array of
 *           integers.
 * Input   : arr - A sorted array of integers. 
 *           n   - Its size.
 *           q   - The number being queried.
 * Returns : The index of the queried number in the array,
 *           or (-1) if it is not found.
 */
int bin_search (const int *arr, int n, int q)
{
  int     i_low;
  int     i_high;
  int     i_mid;

  /* The initial search range is the entire array. */
  i_low = 0;
  i_high = n - 1;

  while (i_high - i_low > 1)
  {
    printf (".");

    /* Find the index of the element at the middle of the current range:
     
           ---------- ( -------------- + -------------- ) ---- 
                     i_low           i_mid            i_high
     */
    i_mid = (i_low + i_high) / 2;

    /* Compare it to q and act accordingly. */
    if (arr[i_mid] == q)
    {
      /* Found the query: */
      return (i_mid);
    }
    else if (arr[i_mid] > q)
    {
      /* Continue with the range to the left of i_mid: */
      i_high = i_mid - 1;
    }
    else
    {
      /* Continue with the range to the right of i_mid: */
      i_low = i_mid + 1;
    }
  }

  /* At this point, the range contains 2 elements (at most), compare them to
     q before giving up. */
  if (arr[i_low] == q)
    return (i_low);
  else if (arr[i_high] == q)
    return (i_high);

  /* If we reached here, q is not found in the array. */
  return (-1);
}