Data structures for searching

Working out how to organise data so that it is easy to work with is an important skill for computer scientists. We also do this in everyday life - for example, some people like to have cutlery nicely organised in a drawer so you can instantly find knives and forks, while others might leave it jumbled up. Both have advantages - the disorganised drawer means you spend a lot less time putting things away, but the organised one makes it easier to find things. Deciding which is the better approach might depend on which of those tasks needs to be done under time pressure.

This also happens if someone is organising notes that they have taken, sets of music that they are about to perform, or books on a shelf. Data structures are simply the way that we organise data.

Fortunately there are some clever approaches that can be fast both for storing away information and finding it, and we explore two of these in this unit: search trees and hash tables. In the process, we’ll not only learn about some commonly used ways for doing searching, but will be introduced to two general ideas (trees and hashing) that keep on coming up as part of clever solutions to challenging problems.