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.

What's it all about?

Searching through items.

The previous lessons in the Searching algorithms unit have shown that the way we organise data can affect which algorithms we can use for searching through it. An unsorted list can't be searched with a binary search; the only way to search through it is to use a sequential search. A sequential search could be used to search a sorted list, but when the list is sorted we can use a binary search, which is a much faster algorithm.

Binary search tree vs hash table.

In computer science, the way we organise data to make it easier to work with is called a data structure. A sorted list is a very simple kind of data structure, where the way it is organised makes binary search possible. In this unit we'll look at two completely different data structures, binary search trees and hash tables, that are commonly used as the basis for searching when it is done …

Read more...
Includes links to computational thinking

Lessons

Ages 11 to 14 Programming challenges
1 Binary search trees No