GCSE
Computer Science
-
Introduction to GCSE Computer Science -
1.1 Systems Architecture -
1.2 Memory and Storage -
1.3 Computer Networks, Connections and Protocols -
1.4 Network Security -
1.5 Systems Software -
1.6 Ethical, Legal, Cultural and Environmental Impacts of Digital Technology -
2.1 Algorithms -
2.2 Programming Fundamentals -
2.3 Producing Robust Programs -
2.4 Boolean Logic -
2.5 Programming Languages and Integrated Development Environments
1. Computer Systems
2.1.3 Searching and Sorting Algorithms
In this lesson, we will explore standard searching algorithms (Binary Search and Linear Search) and standard sorting algorithms (Bubble Sort, Merge Sort, and Insertion Sort). You will understand the main steps of each algorithm, any prerequisites, how to apply them to a data set, and how to identify an algorithm when given its code or pseudocode.
Standard Searching Algorithms
Searching algorithms help locate specific elements in a dataset. Two common methods are binary search and linear search. Binary search quickly finds a target in a sorted list, while linear search checks each element one by one. This means that binary search is faster and more efficient than linear search for large lists and datasets.
Binary Search
The list must be sorted before applying binary search.
- Start with a sorted list of elements.
- Define the search boundaries: low index (start) and high index (end) of the list.
- Calculate the middle index.
- Compare the middle element with the target value.
- If the middle element matches the target value, the search is successful.
- If the target value is smaller than the middle element, update the high index to (middle - 1) and repeat from step 3.
- If the target value is larger than the middle element, update the low index to (middle + 1) and repeat from step 3.
- Continue the process until the target value is found or the low index is greater than the high index, indicating that the value is not in the list.
Example
Data Set: [4, 8, 12, 16, 20, 24, 28]
Target Value: 12
- low = 0, high = 6
- middle = (low + high) / 2 = 3
- 16 (middle element) ≠ 12 (target value) → Update high = 2 (as the element must be less than 16, which is at position 3)
- low = 0, high = 2
- middle = (low + high) / 2 = 1
- 8 (middle element) ≠ 12 (target value) → Update low = 2 (as the element must be more than 8, which is at position 1)
- low = 2, high = 2
- middle = (low + high) / 2 = 2
- 12 (middle element) == 12 (target value) → Search successful!
Linear Search
- Start at the beginning of the list.
- Compare each element sequentially with the target value.
- If the target value is found, the search is successful.
- If the end of the list is reached without finding the target value, the search is unsuccessful.
Example
Data Set: [32, 54, 7, 18, 9, 25]
Target Value: 9
- Compare 32 ≠ 9
- Compare 54 ≠ 9
- Compare 7 ≠ 9
- Compare 18 ≠ 9
- Compare 9 == 9 → Search successful!
*Add advantages
Continue the lesson
This section is available to learners with course access. Continue learning with Knowness to unlock the full explanation, examples, revision tools, and progress tracking.
The remaining lesson content includes further guided explanation, important learning points, and supporting interactive material designed to help you understand and revise this topic.
Unlock this topic to view the full activity, worked examples, common mistakes, and additional revision support.
More content available
Knowness lessons are structured to build understanding step by step. Create an account or upgrade your access to continue from this point.
This preview does not include the hidden lesson text, answers, explanations, or embedded interactions.
Continue learning with Knowness
Sign up to access the full lesson, predicted grades, revision tools, progress tracking, and more.
Create a free accountStandard Searching Algorithms
- Binary Search
- Efficient searching algorithm that requires a sorted list.
- Repeatedly divides the search space in half to find the target.
- Has faster performance than linear search for large datasets.
- The binary search process involves:
- Start with a sorted list.
- Define low and high indexes.
- Compare the middle element with the target.
- Adjust low or high accordingly.
- Repeat until the target is found or the list is exhausted.
- Linear Search
- Works on any list (sorted or unsorted).
- Checks each element one by one until it finds the target or reaches the end.
- Simpler but less efficient than binary search for large lists.
- The linear search process involves:
- Start at the beginning of the list.
- Compare each element to the target.
- Stop if a match is found.
- If no match is found by the end, the target is not present.
Standard Sorting Algorithms
- Bubble Sort
- Compares adjacent elements and swaps them if they’re in the wrong order.
- Repeats passes through the list until fully sorted.
- Easy to understand but inefficient for large data sets.
- The bubble sort process involves:
- Compare adjacent elements and swap if needed.
- Repeat passes through the list.
- Largest values bubble to the end with each pass.
- Stop when the list is fully sorted.
- Merge Sort
- A divide-and-conquer algorithm.
- Splits the list into halves, sorts them recursively, and merges them back.
- More efficient than bubble sort but uses more memory.
- The merge sort process involves:
- Recursively split the list into halves.
- Sort each half.
- Merge the sorted halves back into one sorted list.
- Insertion Sort
- Builds the sorted list one item at a time by inserting elements into the correct position.
- Efficient for small or nearly sorted lists.
- The insertion sort process involves:
- Start with the second element.
- Compare it with previous elements.
- Shift larger elements to the right.
- Insert the current element into its correct position.
Identifying Algorithms from Code or Pseudocode
- Binary search uses loop-based comparison with a middle index.
- Linear search iterates through each element with a simple loop.
- Bubble sort uses nested loops and adjacent swaps.
- Merge sort uses recursion and merging.
- Insertion sort shifts elements until each is placed correctly.