/*
* 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);
}