Meeting 2. Binary search

Thursday September 30

To complete before meeting

  • ✅ Double-check that you have access to the 106M forum where our shared Ed workspaces will be hosted (and while you're there, join in on the Introductions thread!)
  • ✅ Write your own implementation of binary search and test cases to confirm it works correctly. (see below for more information)

Michael and I will be in Lathrop 282 from 2:45-3:15 pm if you want to come by early to finish up your work or ask questions. The class meeting will run 3:15 -4:45 pm.

  • Binary search is a highly efficient algorithm for searching a sorted vector for a target value.
    • Here is the basic gist:
      • Start by comparing the target to the element at the middle index.
      • If the target is less than the middle element, then the target (it exists at all) must be in the first half.
      • Conversely, if the target is greater than the middle element, you only need to look at the elements in the second half.
      • Rinse and repeat on the appropriate half until you find the target or run out of elements to consider.
  • In theory, the algorithm doesn't sound crazy-hard to implement, but the devil is in the details. To summon the proper respect for the task at hand, first read this article written by Mike Taylor Are you one of the 10% of programmers who can write a binary search?
    • The challenge as posed in Mike's article is to write the code without testing or executing it. This means the only tool you have to verify correctness is your own mind. He allows you to take as much time as you want, but even so, this is a tough job!
    • In CS106B, we're huge fans of testing, and happen to think that developing robust, comprehensive test cases for binary search is a pretty interesting task in its own right. So don't take that no-test prohibition so seriously. You are welcome to make a first attempt without testing (if you would find it entertaining), but we want you to follow up with writing good test cases also.
  • Here is the 📦 starter project to use.
    • Before you begin coding, be familiar with this material from 106B:
      • Stanford Vector class (covered in Monday's 106B lecture)
      • Use of SimpleTest framework (covered in last Friday's 106B lecture, used in Assignment 1)
    • The starter project provides an implementation of linear search and its test cases. Review this provided code as a inspiration/model. If there something about our code you don't fully understand or are curious about, make a post on Ed forum to spark discussion.
  • Bring your completed code and test cases to the meeting for show and tell and swapping of war stories. We'll compare and contrast and try to combine our collective work into one pleasing implementation to rule them all. We will also talk through strategies for achieving a robust and comprehensive test suite. Good times will be had by all!

Further resources

Here is some additional reading to peruse if you after finishing the code you have some extra time and further curiosity. The two book chapters can be accessed from the Stanford Library digital collection (click the link below, authenticate with your Stanford sunet, and find link to full book in section labeled "Available online").