Searching: OCR GCSE practice

How does a linear search find an item in a list?

1. It checks the middle item and discards half the list
2. It checks each item in turn, starting from the first
3. It sorts the list first and then checks the last item
4. It checks items at random until it finds the target

Write a program that reads a whole number n, then n names one per line, then a target name. Use a linear search to print the index (counting from 0) of the first name that matches the target, or `Not found` if it is not in the list.

Write a program that reads a whole number n, then n whole numbers in ascending order (one per line), then a target number. Use a binary search to print the index of the target (counting from 0), or -1 if it is not in the list.