Searching, Sorting and Recursion: Quick Revision

A brief note on Searching, Sorting and Recursion. Read it before a test. Try each question at the end before you open its answer.

Searching a list

• Linear search checks the items one by one, from the first. It works on any list, in any order.
• A search function gives back the position, or -1 when the target is not there. Positions start at 0.
• For n items, linear search needs up to n checks.
• target in items answers True or False. items.index(target) gives the first position, but stops with an error when the target is missing.
• Binary search needs a sorted list. It checks the middle item and throws away the half that cannot hold the target.
• The middle is (low + high) // 2. The loop runs while low <= high, and moves to middle + 1 or middle - 1.
• Every check halves the list, so a million sorted items need at most about 20 checks.

Sorting

• sorted(x) gives a new sorted list and leaves x as it was. x.sort() sorts x itself and gives back None.
• reverse=True puts the biggest first. key=len sorts by length, and key=str.lower ignores capital letters.
• A key function is called for each item, and the items are sorted by what it gives back.
• To sort by two things, give back a tuple. (-mark, name) puts the biggest mark first, and equal marks in name order.
• Python's sort is stable: items that are equal by the key keep their old order.
• Bubble sort compares neighbours and swaps them. Selection sort picks the smallest each time. Python's own sorted is faster than both.

Counting the work

• Count the steps, not the seconds. The count is the same on every computer.
• Make a program correct first. Make it faster only when it is too slow.

Recursion

• A recursive function calls itself on a smaller copy of the same problem.
• It needs a base case, which answers without a call, and a recursive case, which moves closer to it.
• With no base case, or a call that is not smaller, Python stops with a RecursionError.
• The calls go down to the base case, and the answers come back up. The waiting calls sit on the call stack.
• Lines before the call run on the way down. Lines after the call run on the way back up.
• For text and lists, take the first item and the rest. The rest is the smaller problem, and the empty one is the base case.
• Folders inside folders hold smaller copies of themselves, so they fit recursion. isinstance(item, dict) tells a folder from a file.
• A loop can do anything that recursion does, and is often faster. The simple recursive Fibonacci repeats the same work again and again.

A worked example

How many times can 40 be halved with // 2 before it reaches 1? This function answers by recursion.

1. On the way down. halvings(40) waits for halvings(20). That one waits for halvings(10), then come halvings(5), halvings(2) and halvings(1).
2. The base case. halvings(1) gives back 0 without another call.
3. On the way back up. Each waiting call adds 1 to the answer that it receives.

The program shows 5. This count is why binary search is fast: a sorted list of 40 items needs at most halvings(40) + 1, that is 6 checks, and not 40.

Practice with new numbers

A program to try

A sports teacher ranks the long jump results, longest first. Then a binary search finds a length in the sorted list, and counts its checks.

Mistakes to avoid

• marks = marks.sort(). sort() gives back None, so the list is lost. Write marks.sort() on its own, or marks = sorted(marks).
• Binary search on a list that is not sorted. There is no error message, only a wrong answer.
• (low + high) / 2 for the middle. A decimal number cannot be a position: TypeError: list indices must be integers or slices, not float. Use //.
• index() for a missing item. [3, 8].index(5) stops with ValueError: list.index(x): x not in list. Ask with in first.
• Sorting numbers and text together. sorted([5, "apple"]) stops with TypeError: '<' not supported between instances of 'str' and 'int'.
• A base case that is never reached. A call that goes 9, 7, 5, 3, 1, -1 never meets n == 0, and ends in RecursionError: maximum recursion depth exceeded.
• No return in the recursive case. The answer is lost, and the caller gets None.

Check yourself

1. A list of 5 000 names is not in order. Gita needs to find one name, only once. Is it worth sorting the list first, so that she can use binary search?

2. A bubble sort takes 3 seconds for 4 000 names. About how long does it take for 8 000 names? And a linear search that takes 0.2 seconds on the shorter list?

3. Leela's function prints a number after its recursive call. What does climb(3) show?

4. Arjun has scores = [("Neel", 64), ("Ojas", 81), ("Pia", 64)]. Write a key function that sorts by score, highest first, with equal scores in name order. In what order do the names come?

5. Sana writes product(items), which multiplies the first item by product(items[1:]). What should the base case give back for an empty list, and why not 0?