Searching and Sorting - A Concise and Practical Introduction to Programming Algorithms in Java - page 134

−

else return Dichotomy( array , left ,m 1, key) ;

}

}

static int DichotomicSearch( int [ ] array , int key)
{ return Dichotomy( array ,0 , array . length − 1, key) ;
}

For example, here is a demonstration program that creates a sorted array of
integers and use the dichotomic search:

public static void main ( String [ ] args )
int [] v= { 1, 6, 9, 12 , 45, 67, 76, 80, 95 } ;

System . out . println ( "Seeking for element 6: Position " +
DichotomicSearch(v,6) ) ; //1
System . out . println ( "Seeking for element 80: Position " +
DichotomicSearch(v,80) ) ; //7
System . out . println ( "Seeking for element 33: Position " +
DichotomicSearch(v,33) ) ; //-1

}

Running this program, the queries yield indices 1, 7 and − 1, respectively. The

last 1 is a code for signaling that the number was not found in the array.

The dichotomic search is exponentially more ecient than the linear search
since the ratio of their time complexity is: O (

−

n

log 2 n ). However to perform a
dichotomic search we need to have sorted arrays. Since it is usually not the
case, let us present now two common sorting methods: the selection sort and
the so-called quicksort.

6.4 Sorting arrays

Given an unsorted array of elements, consider the task of sorting all its elements
to get a sorted array in, say, increasing order. Formally, the only two primitive
operations considered for sorting arrays are:

- comparisons and

- element swapping operations.

For example, these basic operations are implemented as follows for integers:
static boolean GreaterThan(int a, int b)
{return (a>b);}

static void swap (int [] array, int i, int j)