Comparing algorithms, and searching in code

Two algorithms can solve the same problem with very different amounts of work.

At GCSE we compare them by counting steps, usually comparisons, in the worst case.

• Linear search on n items: up to n comparisons. Double the list, double the work.
• Binary search on n sorted items: halve n until nothing is left. Double the list, add one comparison.
• Time taken = number of steps × time for one step.

A worked example: a sorted list holds 2000 items, and a computer makes one comparison every 5 microseconds. A microsecond is one millionth of a second, so 1 000 000 microseconds make 1 second.

1. Linear search, worst case: 2000 comparisons. 2000 × 5 = 10 000 microseconds.

Algorithms here are shown as pseudocode (in two common styles) or as Python.

Pick your style with the buttons above any code; your choice is remembered.

Pseudocode is code written for people to read: it looks like a programming language but does not run on a computer. The programming unit teaches code in full. To read the code in this lesson you need these pieces:

• x = 5 (or x ← 5) puts the value 5 into the variable x, a named store for a value. == (or a single = in AQA style) asks whether two values are equal.
• items = [12, 5, 31, 8] is a list. items[0] is the item at index 0, here 12. items.length, LEN(items) and len(items) all give the number of items, here 4.
• if ... then ... endif runs the lines inside only when the condition is true.
• while condition ... endwhile repeats the lines inside for as long as the condition is true.
• for i = 0 to 3 ... next i repeats the lines inside with i = 0, then 1, 2 and 3. In Python, for i in range(len(items)) does the same: i goes from 0 to one less than the number of items.
• print(x) (or OUTPUT x) shows the value of x.

A worked example: this program finds the smallest number in a list.

nums = [40, 17, 52, 9, 23]
low = nums[0]
for i = 1 to nums.length - 1
    if low > nums[i] then
        low = nums[i]
    endif
next i
print(low)

nums ← [40, 17, 52, 9, 23]
low ← nums[0]
FOR i ← 1 TO LEN(nums) - 1
    IF low > nums[i] THEN
        low ← nums[i]
    ENDIF
ENDFOR
OUTPUT low

nums = [40, 17, 52, 9, 23]
low = nums[0]
for i in range(1, len(nums)):
    if low > nums[i]:
        low = nums[i]
print(low)

1. low starts as the first item, 40.

If a loop sets a variable every time it finds a match, the variable ends up holding the last match, because each match replaces the one before.

items = [12, 5, 31, 8]
target = 31
found = false
i = 0
while found == false AND i < items.length
    if items[i] == target then
        found = true
    endif
    i = i + 1
endwhile
print(i)

items ← [12, 5, 31, 8]
target ← 31
found ← False
i ← 0
WHILE found = False AND i < LEN(items)
    IF items[i] = target THEN
        found ← True
    ENDIF
    i ← i + 1
ENDWHILE
OUTPUT i

items = [12, 5, 31, 8]
target = 31
found = False
i = 0
while found == False and i < len(items):
    if items[i] == target:
        found = True
    i = i + 1
print(i)

mid = (low + high) DIV 2
if items[mid] == target then
    found = true
elseif items[mid] < target then
    low = mid + 1
else
    high = mid - 1
endif

mid ← (low + high) DIV 2
IF items[mid] = target THEN
    found ← True
ELSE IF items[mid] < target THEN
    low ← mid + 1
ELSE
    high ← mid - 1
ENDIF

mid = (low + high) // 2
if items[mid] == target:
    found = True
elif items[mid] < target:
    low = mid + 1
else:
    high = mid - 1

Practise writing both in Python: Searching and Counting steps on Brainlag Code.

A trace table records the value of each variable as a program runs, so you can check what it does by hand.

1. One column for each variable, and one for output if there is any.

For a while loop, check the condition with the current values before every pass. The loop stops the first time it is false.