import java.util.Arrays;// This program demonstrates a few of the search and sort algorithmspublic class ArrayDemo{ // Linear search public static int linearSearch( int[] a, int key ){ for( int i=0; i<a.length; i++ ) if ( a[i] == key ) return i; return -1; } // Binary search (assume sorted array) public static int binarySearch( int[] a, int key ){ return binarySearch(a, key, 0, a.length-1); } public static int binarySearch( int[] a, int key, int from, int to ){ if(to < from) return -1; int middle = (from + to + 1)/2; if(key == a[middle]) return middle; else if( key < a[middle] ) return binarySearch( a, key, from, middle-1 ); else return binarySearch( a, key, middle+1, to ); } // Selection sort public static void selectionSort( int[] a ){ for( int i=0; i < a.length-1; i++ ) { int smallest = i; for( int j=i+1; j < a.length; j++ ) if( a[j] < a[smallest] ) smallest = j; swap(a,i,smallest); } } // Insertion sort public static void insertionSort( int[] a ){ for( int i=0; i < a.length; i++ ) { int k=i; for(int j=i-1; j>=0; j--) if( a[j] > a[k] ){ swap(a,j,k); k=j; } } // end of outer for-loop } public static void printArray(int[] a){ System.out.print("The array is: "); for(int n:a) System.out.print(n+" "); System.out.println(); } private static void swap( int[] a, int first, int second ){ int temp = a[first]; a[first] = a[second]; a[second] = temp; } public static void main( String args[] ){ int[] array = {2,3,1,8,5,1,13,11}; int key = 3; int pos; printArray(array); // Searching using linear search pos = linearSearch( array, key ); System.out.println("Linear search finds " + key + " at position " + pos); // Sorting using selection sort or insertion sort //insertionSort(array); selectionSort(array); System.out.println("Sorting the array..."); printArray(array); // Searching using binary search pos = binarySearch( array, key ); System.out.println("Binary search finds " + key + " at position " + pos); }}