/**
  John P. Cataldo &lt;cataldoj@ccs.neu.edu&gt;<br>
  Daniel Rinehart &lt;danielr@ccs.neu.edu&gt;<br>
  Aris Yannopoulos &lt;aris@ccs.neu.edu&gt;<br>
  COM1390 Programming Assignment #1<P>

  $Id: BinaryInsert.java,v 1.6 1999/02/16 02:42:04 danielr Exp $<P>

  Find where an item should be inserted into the array given that the
  array is already sorted.

  */
public class BinaryInsert {
  //-- METHODS --

  // returns [ index, numberOfComparisons ]

  /**

    Return the position where x should be inserted before given a
    sorted array of number.

    @param list the list of sorted numbers
    @param x the element to insert

    @return the index which x should be inserted before 

    */
  public static int binaryInsert( int[] list, int x ) {

    boolean[] checked = new boolean[ list.length ];
    boolean[] greaterThanList = new boolean[ list.length ];
    for ( int q = 0 ; q < checked.length ; q++ )
      checked[ q ] = false;

    boolean found = false;
    boolean wentUp = true;
    int dir = 1;
    int comp = 0;
    boolean greaterThan = true;

    int index = list.length / 2; 

    // how much of the list will need to be examined after this iteration
    int split = index;

    int oldindex = index;
    while ( ! found ){
      checked[ index ] = true;

      comp++;
      greaterThan = ( x > list[ index ] );
      greaterThanList[ index ] = greaterThan;
      if ( greaterThan ) { 
	dir = 1;

	if ( index == ( list.length -1 ) ){
	  found = true;
	}
      } else { 
	dir = -1;

	if ( index == 0 )
	  found = true;
      }

      if ( split < 1 ) {
	found = true;

      }

      index += ( dir * ( split / 2 + ( split % 2 )));


      //we've moved back to a spot previously compared
      //this can only happen when S is ~= 1
      if ( ( index >= 0 ) && ( index < list.length ) ){

	if ( checked[ index ] ){
	  found = true;
	  if ( greaterThanList[ index ] )
	    index++;
	  
	}
      }

      //NO MOVEMENT
      if ( index == oldindex ){
	found = true;
	if ( greaterThan ){
	  index++; //place x after this element
	}
      }
      
      split = ( split / 2 );  //ceiling
      oldindex = index;
    }

    if ( index < 0 ) index = 0;
    
    FindQuantiles.incComp( comp );
    
    return( index );
  }
}