Search Algorithms

What are searching algorithms?

Search algorithms are algorithms designed to find items in an an array(list). If the item is found in the search the the algorithm will return the index(position) of the item in the array. If an array contains duplicates of an item being searched for it will normally return the index of the first instance that it finds.

Example

In the array of cards below , if you searched for the item ‘4 of clubs’, the algorithm would return the integer 1.

Note how indexing begins at 0, not 1.

*Some languages, such as Scratch would return 2, as they start counting at 1 instead of 0.

What happens if the item is not in the array?

If the item is not found then depending on the programming different things will happen:

Python – It will raise an exception (ERROR!!!)
JavaScript – It will return -1 (JavaScript arrays start indexing from zero)
Scratch – It return Zero (Scratch lists are 1 based because it’s a blocks based language designed for children)

Linear Search

AS & A Level – You are required to know how it works and be able to write Code / Pseudocode for the algorithm

The linear search(a.k.a sequential search) algorithm is a simple search algorithm that starts at the left hand side of an array (index 0) and moves through the array one item at a time. Once the item being searched for is found the algorithm returns the index of the item in question. If the algorithm reaches the end of the array without finding the item then it either returns an error or it returns a non valid index depending on the implementation.

Example Python Code Implementation of Linear Search

How does my implementation above differ to standard Python in the way it handles linear search?

Binary Search

A Level Only – You are required to know how it works and be able to write Code / Pseudocode for the algorithm

Linear search is very effective but it is also quite inefficient, especially for very large arrays. If the array in question is an ordered array where all the items have been sorted, then an alternative such as Binary search can be used instead, which is far more efficient for larger arrays because it uses a divide and conquer methodology.

You would be able to perform Binary search on this array of cards as it is ordered.

Performance

Factors affecting search performance

Ordering of the items in the array.
Size of the array
Choice of algorithm

Exam

Practice Exam Questions

2015 Specimen Paper / Mark Scheme

Factors affecting search performance – initial data order, choice of search algorithm, size of array