SearchingSearching an array of integersSearching an array of StringsSearching an array of ObjectsTemplatesReview: Overriding methodsJava review: equalsOverriding equalsAbout sorted arraysThe Comparable interfaceRules for implementing ComparableConsistency with equalsBinary searchBinary search algorithm (p. 43)Example of binary searchBinary search in Java (p. 45)Recursive binary search in JavaStrings of bitsLogarithmsRelationshipsLogarithms—a summaryBinary search takes log n timeConclusionThe EndSearching2Searching an array of integersIf an array is not sorted, there is no better algorithm than linear search for finding an element in it static final int NONE = -1; // not a legal index static int linearSearch(int target, int[] a) {for (int p = 0; p < a.length; p++) {if (target == a[p]) return p;}return NONE;}3Searching an array of StringsSearching an array of Strings is just like searching an array of integers, exceptInstead of int1==int2 we need to use string1.equals(string2) static final int NONE = -1; // not a legal index static int linearSearch(String target, String[] a) {for (int p = 0; p < a.length; p++) {if (target.equals(a[p])) return p;}return NONE;}4Searching an array of ObjectsSearching an array of Objects is just like searching an array of Strings, providedThe operation equals has been defined appropriately static final int NONE = -1; // not a legal index static int linearSearch(Object target, Object[] a) {for (int p = 0; p < a.length; p++) {if (target.equals(a[p])) return p;}return NONE;}5TemplatesThere is no way, in Java, to write a general linear search method for any data typeWe can write a method that works for an array of objects (because Object defines the equals method)For arbitrary objects, equals is just ==For your own objects, you may want to overridepublic boolean equals(Object o)The parameter must be of type Object!The method we defined for Objects also works fine for Strings (because String overrides equals)A search method for objects won’t work for primitivesAlthough an int can be autoboxed to an Integer, an int[] cannot be autoboxed to an Integer[]6Review: Overriding methodsTo override a method means to replace an inherited method with one of your ownYour new method must be a legal replacement for the inherited versionConsequences:Your new method must have the exact same signature (name, order and types of parameters—but parameter names are irrelevant)Your new method must have the same return typeYour new method must be at least as public as the method it replacesYour new method can throw no new exceptions that the method being overridden doesn’t already throwIn Java 5 and later, you should put @Override in front of your methodThis lets the compiler check that you got the signature right7Java review: equalsThe Object class definespublic boolean equals(Object obj)For most objects, this just tests identity: whether the two objects are really one and the sameThis is not generally what you wantThe String class overrides this method with a method that is more appropriate for StringsYou can override equals for your own classesIf you override equals, there are some rules you should follow8Overriding equalsIf you override equals, your method should have the following properties (for your objects x, y, z)Reflexive: for any x, x.equals(x) should return trueSymmetric: for any non-null objects x and y, x.equals(y) should return the same result as y.equals(x)For any non-null x, x.equals(null) should return falseTransitive: if x.equals(y) and y.equals(z) are true, then x.equals(z) should also be trueConsistent: x.equals(y) should always return the same answer (unless you modify x or y, of course)Java cannot check to make sure you follow these rules9About sorted arraysAn array is sorted in ascending order if each element is no smaller than the preceding elementAn array is sorted in descending order if each element is no larger than the preceding elementWhen we just say an array is “sorted,” by default we mean that it is sorted in ascending orderAn array of Object cannot be in sorted order !There is no notion of “smaller” or “larger” for arbitrary objectsWe can define an ordering for some of our objects10The Comparable interfacejava.lang provides a Comparable interface with the following method:public int compareTo(Object that)This method should returnA negative integer if this is less than thatZero if this equals thatA positive integer if this is greater than thatReminder: you implement an interface like this: class MyObject implements Comparable { public int compareTo(Object that) {...}}11Rules for implementing ComparableYou must ensure:x.compareTo(y) and y.compareTo(x) either are both zero, or else one is positive and the other is negativex.compareTo(y) throws an exception if and only if y.compareTo(x) throws an exceptionThe relation is transitive: (x.compareTo(y)>0 && y.compareTo(z)>0) implies x.compareTo(z)>0if x.compareTo(y)==0, then x.compareTo(z) has the same sign as y.compareTo(z)You should ensure: compareTo is consistent with equals12Consistency with equalscompareTo is consistent with equals if: x.compareTo(y)==0 gives the same boolean result as x.equals(y)Therefore: if you implement Comparable, you really should override equals as wellJava doesn’t actually require consistency with equals, but sooner or later you’ll get into trouble if you don’t meet this condition13Binary searchLinear search has linear time complexity:Time n if the item is not foundTime n/2, on average, if the item is foundIf the array is sorted, we can write a faster searchHow do we look up a name in a phone book, or a word in a dictionary?Look somewhere in the middleCompare what’s there with the thing you’re looking forDecide which half of the remaining entries to look atRepeat until you find the correct placeThis is the binary search algorithm14Binary search algorithm (p. 43)To find which (if any) component of a[left..right] is equal to target (where a is sorted):Set l = left, and set r = rightWhile l <= r, repeat:Let m be an integer about midway between l and rIf target is equal to a[m], terminate with answer mIf target is less than a[m], set r = m–1If target is greater than a[m], set l = m+1Terminate with answer none• • •• • •l
View Full Document
Unlocking...