private void locate ( double [ ] array , int left , int right , int index ) { int mid = ( left + right ) / 2 ; //System.out.println(left+" to "+right+" ("+mid+")"); if ( right == left ) { //System.out.println("* "+array[targetIndex]); //result=array[targetIndex]; return ; } if ( left < right ) { double s = array [ mid ] ; int i = left - 1 ; int j = right + 1 ; while ( true ) { while ( array [ ++ i ] < s ) ; while ( array [ -- j ] > s ) ; if ( i >= j ) break ; swap ( array , i , j ) ; } //System.out.println("2 parts: "+left+"-"+(i-1)+" and "+(j+1)+"-"+right); if ( i > index ) { // the target index in the left partition //System.out.println("left partition"); locate ( array , left , i - 1 , index ) ; } else { // the target index in the right partition //System.out.println("right partition"); locate ( array , j + 1 , right , index ) ; } } }
sort the partitions by quick sort and locate the target index