Computer Science A2 · Computational thinking and Problem-solving. The idea in plain words, the rules to remember, the mistake to avoid and a worked example, written and checked by Mega Lecture.
A linear search checks each item in turn, so it works on any list. A binary search needs the items in order: it looks at the middle item and throws away the half that cannot hold the target, again and again.
Bubble sort compares neighbours and swaps them if they are in the wrong order. Insertion sort takes each item and moves it back into its correct place in the sorted part. Both are fast on data that is nearly sorted and slow on large, mixed-up data.
An Abstract Data Type (ADT) is a set of data with the operations allowed on it: stack, queue, linked list, binary tree, dictionary and graph. Algorithms are compared with Big O notation for time and memory.
Students use a binary search on unsorted data, or write Low ← Mid and High ← Mid. The middle item has already been checked, so use Mid + 1 and Mid − 1, or the search may never end.
Answer: 4 comparisons (items 27, 40, 31, 36). A linear search would need 8.
Type what you are stuck on. The helper finds the explanation, worked examples and the notes to read, free and instant.
← Artificial Intelligence (AI)Recursion →Take a Computer Science A2 test