Big Picture

Described control structures can be used in algorithms.

Past

Describe techniques that can be used for a searching algorithm.

Demonstrate a range of searching algorithms and evaluate their characteristics.

Present

Future

Careers: Software Developer, Programmer.

An algorithm is a step by step set of instructions for a computer to follow.

There are many different methods that can be used to search for data in a computer.

Some algorithms are more efficient at finding data or some are simpler to program. The two techniques you need to know for the exam are:

Searching Algorithms

• Linear Search

• Binary Search

Finds the middle point of the search list. Halves the list each time until it finds the value you are searching for.

List must be sorted to work but works efficiently on large lists, bit is more complex to program.

Binary Search

Searches through one index at a time until it finds the desired item.

Stops the search after it finds the first value. Easy to program but inefficient on large lists.

Linear Search

Overview Comparison

Linear Search

If we use the list below and search for D. The algorithm will start at index 0, it will check to see if D is at position 0.

If not it will move on to index location 2. It will continue this process until index 4. It has found the search will stop and it will display the location.

​Flowchart of a linear search

Linear Search

You do not need to remember the code for this algorithm but you must be able to recognise it.

Binary Search

Binary search also known as divide and conquer is more efficient for larger lists but can only be done on a ordered list.

We find the middle value of the list. If the list is of 50 numbers we would find the value at index 25. If the number we searched is higher we disregard 0-25 and repeat the technique with 26-50

This continues until we are left with the searched value.

​Flowchart of a linear search

Binary Search

You do not need to remember the code for this algorithm but you must be able to recognise it.

Binary Search

You may need to demonstrate the search. Here we search for G.

To work out middle value add first and last position and divide by 2. Here it is 0 + 10 / 2= 5.

G is in position 6 so we disregard all values from 0-5 and repeat. 6 + 10 / 2 = 8.G is in position 6 so we disregard the right side of the list. We repeat again to desired value.

Written example

Main Task

Computer Task:
Create an algorithm PowerPoint that summarises the information for each search technique. You should have a written description of how the search works including the benefits and drawbacks.

Use the internet to find pseudocode and flowcharts to represent each search algorithm. Analyse the code on each to identify the main give aways of each.

Complete all the questions on the work sheet.