CSC151 2007S, Class 43: Binary Search Admin: * Questions on HW14? * Can we use an anonymous procedure in defining tally-as? YES! * EC for Kesho Scott lecture or Ferrett/Stewart * EC for signing up for Psych Experiments conducted by your classmates. * EC for participating in ONE pride week activity Overview: * About common algorithms. * Searching. * Binary search. * Lab. /Computer Science is the Study of Algorithms/ * Algorithm is a set of instructions for building a solution to a problem * These past ten or so weeks: * Tools for expressing algorithms * Some problems in a variety of domains * Computer scientists also try to identify common problems and then to write "the best possible" algorithm for solving those problems * This week and next: Two common problems (and some famous solutions) * Searching - Given a collection of stuff, find something in the collection that meets particular criteria * Common type: Using "keyed values", find a value with a particular key * Sorting * Put things in order (typically using a key) /Binary Search/ * Searching in a particular domain * Keyed values * Stored in an array * Ordered from smallest key to largest key * Strategy: * Look in the middle of the remaining things * FOund it - Done * Middle is too small, throw away the left half * Middle is too large, throw away the right half /Lab/ /Reflection/ * How do you know that the response from binary-search is correct? Hint: vector-ref * Testing count-grades try using a grade of 11 (how many grades are less than 11) try using a grade of 256 (how many grades are less than 256) * Emily's third-favorite part of 151 - The binary search demo