April 7th 2014 public class Lecture4 1 Tips for testing Testing input think of limited set of tests likely to expose bugs boundary cases positive zero negative numbers right at the edge of an array or collection s size empty cases and error cases 0 1 null an empty list or array test behavior in combination 2 Searching methods indexOf returns first index of element or 1 if not found contains returns true if value is in the array isEmpty contains indexOf makes things convenient Returns first index at which value is found public int indexOf int value for int i 0 i size i if elementData i value get i value return i return 1 went through all values didn t find value Returns true if value is in array public boolean contains int value if indexOf value 0 return true else return false return indexOf value 0 3 Sequential Search locates target value in an array list by examining each element from start to finish Used in indexOf 4 Binary search locates target value in a sorted array or list by successively elimination half of the array from consideration 5 Arrays binarySearch Arrays binarySearch array value searches an entire sorted array for a given value Returns its index if found a negative number if not Pre condition array is sorted Arrays binarySearch array minIndex maxIndex value searches given portion of a sorted array for a given value examines minIndex inclusive through maxIndex exclusive Returns its index if found a negative number if not found pre condition array is sorted binarySearch method in the Arrays class searches an array very efficiently if the array is sorted if value is not found binary search returns insertionPoint 1 where insertionPoint is the index where the element would have been if it had been in the array in sorted order 6 Runtime efficiency efficiency measure of computing resources used by code can be relative to speed time memory space etc most commonly refers to run time assume the following any single java statemenet takes same amount of time to run a method call s runtime is emasured by the total of the statements inside the method s body a loop s runtime if the loop repeats N times is N times the runtime of the statements in its body 7 Algorithm growth rates measure runtime in proportion to input data size N growth rate change in runtime as N changes Consider the runtime when N is extremely large highest order term dominates overall runtime we say this algorithm runs on the order of N 3 or O N 3 big Oh of N cubed nested loops on some kind of lists are very expensive DON T WANT 8 Complexity classes a category of algorithm efficiency based on the algorithm s relationshp to the input size N constant O 1 unchanged when N doubles 9 Efficiency Sequential search O N as array size grows so does runtime add O 1 add index value O N indexOf O N get O 1 remove O N set O 1 size O 1 change complexity classes but don t cut out small things binarySearch log2 N Logarithmic complexity class