//####################################################################
// This program is an implementation of binary search.
// First an array is filled with random 4-digit integers, then bubble
// sort is used to sort the array. A number is randomly picked from
// the array and binar search is used to search that number.
//####################################################################
#include <stdio.h>
#include <stdlib.h>

int binary_search(int val, int arr[], int size)
{
   int left = 0, right = size-1, middle;
   int iter=0;

   do {
      middle = (left + right) / 2;
      printf("##### Iteration %2d: left= %d  middle= %d  right= %d\n",
              ++iter, left, middle, right);
      if(arr[middle] < val)
         left = middle + 1;
      else if(arr[middle] > val)
         right = middle - 1;
      else
         return middle;
   } while(left <= right);  // (left < right) won't work

   return -1;
}

#define SIZE 10

void bubble_sort(int arr[], int size);

int main()
{
    int a[SIZE], i, waldo, res;
    srand(1); // seed.

    // fill the array with random 4-digit numbers
    for(i=0; i<SIZE; i++)
        a[i] = rand()/(RAND_MAX+1.0) * 9000 + 1000;

    // sort the array with bubble sort
    bubble_sort(a, SIZE);

    // randomly pick a number from the array
    waldo = a[(int)(rand()/(RAND_MAX+1.0) * SIZE)];

    printf("Searing for %d  in array:\n", waldo);
    for(i=0; i<SIZE; i++)
        printf("%4d  ", i);
    printf("\n");
    for(i=0; i<SIZE; i++) {
        printf("%4d  ", a[i]);
	if((i+1)%10 == 0)
	    printf("\n");
    }
    printf("\n\n");

    //search the number waldo with binary search
    res = binary_search(waldo, a, SIZE);
    if(res == -1)
        printf("%d not found!\n", waldo);
    else
        printf("%d at index %d!\n", waldo, res);

}

void bubble_sort(int arr[], int size)
{
   int i, j, temp;
   for (i=0; i<size-1; i++)
   {
      for (j=size-1; j>i; --j)
      {
         if (arr[j] < arr[j-1]) {
            temp = arr[j];
            arr[j] = arr[j-1];
            arr[j-1] = temp;
         }
      }
   }
}