19 Computational thinking and Problem-solving
19.1 Algorithms
LINEAR & BINARY SEARCH
In this comprehensive guide, we will explore fundamental algorithms and data structures essential for computer
science students progressing from secondary school to A-level studies. By the end of this chapter, you should be
able to:
Understand and implement linear and binary search algorithms.
Comprehend the conditions necessary for the effective use of binary search.
Analyze how the performance of binary search varies with the number of data items.
Understand insertion sort and bubble sort methods.
Recognize that the performance of a sorting routine may depend on the initial order of the data and the
number of data items.
Understand and use Abstract Data Types (ADTs).
Implement ADTs from other ADTs.
Describe and implement the following ADTs: stack, queue, linked list, dictionary, binary tree.
Write algorithms to:
o Implement an insertion sort.
o Implement a bubble sort.
o Find an item in each of the following: linked list, binary tree.
o Insert an item into each of the following: stack, queue, linked list, binary tree.
o Delete an item from each of the following: stack, queue, linked list.
Understand that a graph is an example of an ADT.
Describe the key features of a graph and justify its use for a given situation.
Understand that different algorithms performing the same task can be compared using criteria such as
time taken to complete the task and memory used.
Understand Big O notation for time and space complexity.
1. Search Algorithms
1.1 Linear Search
Definition: Linear search, also known as sequential search, involves checking each element in a list one by one
until the desired element is found or the list ends.
Algorithm:
1. Start from the first element of the list.
2. Compare the current element with the target value.
3. If they match, return the index of the current element.
4. If not, move to the next element.
5. Repeat steps 2-4 until the element is found or the list ends.
Implementation in Python:
def linear_search(arr, target):
for index, value in enumerate(arr):
if value == target:
return index
return -1
Time Complexity: O(n), where n is the number of elements in the list. In the worst case, the algorithm checks
every element.
Space Complexity: O(1), as it uses a constant amount of extra space.
1.2 Binary Search
Definition: Binary search is an efficient algorithm for finding an item from a sorted list by repeatedly dividing
the search interval in half.
Conditions for Use:
The list must be sorted.
Random access to elements is possible.
Algorithm:
1. Initialize two pointers, low at the start and high at the end of the list.
2. While low is less than or equal to high:
o Calculate the middle index: mid = (low + high) // 2.
o If the middle element matches the target, return mid.
o If the target is less than the middle element, adjust high to mid - 1.
o If the target is greater, adjust low to mid + 1.
3. If the element is not found, return -1.
Implementation in Python:
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
Time Complexity: O(log n), as the search space is halved with each step.
Space Complexity: O(1) for the iterative approach; O(log n) for the recursive approach due to the call stack.
Performance Analysis: Binary search is significantly faster than linear search for large datasets, but it requires
the data to be sorted. In contrast, linear search does not require sorted data but is less efficient for large lists.
