Laboratory Exercise 9
CSci 227: Programming Methods
Department of Computer Science
Hunter College, City University of New York
Spring 2024

Learning Objectives:

To be able to explain and implement sequential search and binary search.
To understand the idea of hashing as a search technique.
To analyze running times of algorithms that use sequential search, binary search, and hashing.

Software Tools Needed: Web browser to access textbook and an IDE (on-line or on computer) with core Python 3.6+ loaded.

Linear Search

A brute force way to find something in a list of items is to start at the beginning, and look at each one until the item is located. Or until you have looked at everything and determined it's not in the list. This approach is called linear search or sequential search. Work through the textbook section, thinking about the running time of the algorithm:

Binary Search

If your list of items has some order, then you can be much more efficient about searching for items. The standard approach is called binary search. Work through the textbook section, thinking about the running time of the algorithm:

Hashing as Searching

The chapter ends with hashing as searching:

Quizzes and Code Reviews

There are weekly written quizzes and code reviews in 1001G, 11:30-5:30, Mondays-Fridays when classes are in session. No appointments are needed for CSCI 227 students. Make sure to complete Quiz 9 and Code Review 9 by Thursday, 11 April.

Additional Practice

For additional practice on core Python, see the HackerRank prepare series:

HackerRank: Prepare Python

Click the Medium option on the right hand menu, and work through their Python challenges.

For more practice on searching techniques to solve problems, here are some popular ones from LeetCode: