/* Array search and insert demonstration program.                 */
/* Copyright by Rick Wagner, March 17, 1999, all rights reserved. */
/* Created for use in USC's Computer Science 101.                 */

#include <stdio.h>
#include <string.h>

/* Function prototypes: */
void insert(char, char*);
void search(int*, char, char*, int, int);

void main()
{
  int i = 0;
  int iLength = 0;

  char cA[9] = {'r', 'o', 'a', 'd', 'k', 'i', 'l', 'l', '\0'};
  char cB[9];

  puts("Array search and insert demonstration program.");
  puts("Copyright by Rick Wagner, March 17, 1999, all rights reserved.");
  puts("Created for use in USC's Computer Science 101.");
  puts("");

  cB[0] = '\0';
  iLength = strlen(cA);

  for (i = 0; i < iLength; i++)
  {
    insert(cA[i], cB);
  }

  printf("1 %s\n", cA);
  printf("2 %s\n", cB);
  printf("\n\n");
}

void insert(char c, char* cArray)
{
  int i = 0;
  int iPosition = 0;
  int iLength = 0;

  iLength = strlen(cArray);
  search(&iPosition, c, cArray, 0, iLength - 1);

  for (i = iLength; i > iPosition; i--)
  {
    /* Move the position character and those on the right one space to the right. */
    cArray[i] = cArray[i - 1];
  }
  cArray[iPosition] = c;
  cArray[iLength + 1] = '\0';  /* Put in the null character string terminator  */
}

void search(int* ptrPosition, char c, char* cArray, int iLeft, int iRight)
{
  /* Assumes the array to be searched is sorted */
  int iMiddle = 0;

  if (iRight - iLeft > 0)
  {
    /* There is at least one character in the array */
    int iMiddle = (iLeft + iRight) / 2;       /* Integer division */
    if (c > cArray[iMiddle])
    {
      /* Search the right half of the array: */
      search(ptrPosition, c, cArray, iMiddle + 1, iRight);
    }
    else
    {
      /* Search the left half of the array: */
      search(ptrPosition, c, cArray, iLeft, iMiddle);
    }
  }
  else
  {
    *ptrPosition = iLeft;
  }
}