// Illustrates linear and binary search of a sorted array of ints // DIS modifying Fall 1999 file import java.util.*; // need for sort public class SearchIntArray { public static void main(String[] args) { int length = Integer.parseInt(args[0]); int key = Integer.parseInt(args[1]); int[] a = new int[length]; for (int i = 0; i < a.length; i++) a[i] = MyMath.randInt(1,10); print(a); Arrays.sort(a); // need sorting for binary search print(a); System.out.println("Linear search " + linearSearch(a,key)); System.out.println("Binary search " + binarySearch(a,key)); } // linear search on possibly unsorted array: public static boolean linearSearch(int[] a, int key) { int i = 0; while (i < a.length) if (a[i] == key) return true; else i++; return false; } // binary search on sorted array // left and right are the two end points of interval: public static boolean binarySearch(int[] a, int key) { int left = 0; int right = a.length - 1; int middle; while (left <= right) { middle = (left + right)/2; if (key==a[middle]) return true; else if(key < a[middle]) right = middle-1; else left = middle+1; } // if we reach here, we didn't find the object: return false; } // display array: public static void print(int[] a) { for (int i = 0; i < a.length; i++) System.out.print(a[i]+" "); System.out.println(); } } class MyMath { // Return a random int between low and high, inclusive: public static int randInt(int low, int high) { return (int) (Math.random()*(high-low+1)) + (int) low; } }