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.
In the array of cards below , if you searched for the item ‘4 of clubs’, the algorithm would return the integer 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!!!)
- Scratch – It return Zero (Scratch lists are 1 based because it’s a blocks based language designed for children)
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?
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.
Factors affecting search performance
- Ordering of the items in the array.
- Size of the array
- Choice of algorithm