Standard Searching Algorithms (OCR GCSE Computer Science): Revision Notes

Standard Searching Algorithms

Searching algorithms are used to find a specific item in a list. The two main types are Linear Search and Binary Search. Each has different steps, uses, and efficiency depending on the dataset.

Linear Search

• A linear search examines each item in the list one by one.
• You start at the first item and check if it's the one you're looking for.
• If it's not, move to the next item and repeat until you find the item or reach the end of the list.
• This method works on unsorted lists.

Method

1. Look at the first item in the list.
2. If it matches the item you're searching for, stop.
3. If not, move to the next item.
4. Repeat this process until the item is found or the end of the list is reached.

Worked Example

Binary Search

• A binary search is a divide-and-conquer algorithm.
• It requires the list to be sorted before searching.
• The list is repeatedly divided in half, which reduces the number of items to search through.

Method

1. Ensure the list is sorted.
2. Find the middle item in the list.
3. If the middle item is what you're looking for, stop.
4. If the item you're searching for is less than the middle item, search the left half of the list.
5. If the item you're searching for is greater than the middle item, search the right half of the list.
6. Repeat the process until the item is found or there are no items left to search.

Worked Example

Comparing Linear Search and Binary Search

Linear Search	Binary Search
Can be used on unsorted lists.	Requires the list to be sorted first.
Slower for large lists as it checks every item one by one.	Faster for large lists, cutting the search area in half each time.
Simple to implement.	More efficient, but requires extra steps to sort the list first.