Choosing the right searching technique

Overview

Matching the technique to the data — a short unsorted list, a large sorted array queried constantly, a weighted network — and the cost of keeping data sorted in the first place.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   Which search technique suits a small unsorted list?

   Model answer

   A linear search suits a small unsorted list because no preparation is needed. The cost of sorting first would outweigh any saving.

2. 2

   Which search technique suits a large sorted array that is queried often?

   Model answer

   A binary search suits a large sorted array because each comparison halves the work. Millions of items are searched in about twenty comparisons.

3. 3

   Which technique is used to find the cheapest route through a network of nodes?

   Model answer

   A shortest-path algorithm such as Dijkstra's is used for a weighted network. A simple list search cannot handle connections between items.

4. 4

   Why does the cost of keeping data sorted affect the choice of search?

   Model answer

   Every insertion into a sorted list must preserve the order, which costs time. A list updated constantly may be cheaper to search linearly.

5. 5

   Which technique would a satellite navigation system use to plan a journey?

   Model answer

   A shortest-path algorithm is used because the road network is a weighted graph. The weights represent distance or expected travel time.

6. 6

   Which technique would suit finding a record in a hash table?

   Model answer

   A hash table avoids searching altogether because the key is converted directly into an address. A short search of the overflow area is needed only after a collision.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.