2.1 Search Algorithms

Question 1

What is a search algorithm

Answer 1

• A search algorithm is a set of instructions for finding a specific item of data within a data set.
• Computer systems can store and process billions of pieces of data so it is vital that computers can find the information they need efficiently.

Question 2

Effective searching

Answer 2

An effective search is one which will always either find the solution or determine that the target data is not present.

Question 3

Efficient searching

Answer 3

An efficient search will find the solution quickly regardless of its location within the data set.

Question 4

What are the two common search algorithms

Answer 4

Linear search
Binary search

Question 5

Linear Search

Answer 5

• Check the first item in the dataset:
  
  • If it is what we are looking for, return it.
• Check the second item in the dataset:
  
  • If it is what we are looking for, return it.
• Continue for rest of items.
• If we reach the end of the data set, then the item was not in our data set.

Question 6

Pros and cons of linear search

Answer 6

Easy to implement

Slow on a long list

Question 7

Binary search

Answer 7

• Find the middle of the dataset.
• If the middle value is greater than the target then:
  
  • Repeat on the first half of dataset.
• If the middle value is lesser than the target then:
  
  • Repeat on the second half of dataset.
• If the middle value is the target:
  
  • We found it!
• Stop repeating once the size of our dataset is zero.

Question 8

Pros and cons of binary search

Answer 8

Faster than linear search on a large data base

Dataset must be sorted before starting