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