Search Algorithms - Word Drop

A ______ starts at the first item and compares it with the ______, the item being looked for. It works through the list one item at a time until a match is found or the end is reached. It has no pre-requisite, so it also works on an ______ list. In code, it uses a single ______ that starts at the first position and counts up by one each time.

A ______ needs the list to be sorted first. It compares the target with the middle item, found with mid = (low + high) // 2. If the target is larger, the search ______ everything before the middle item, so low becomes mid + 1. If the target is smaller, high becomes mid - 1.

The search repeats until the item is found, or until low is ______ than high, when nothing is left to check. Searching 1, 8, 16, 17, 18, 19, 25 for 20 ends with low above high, so the answer is ______.

On a large sorted list a binary search makes far fewer ______ than a linear search, because each comparison removes half of the items left, but the data must be sorted first. A linear search is ______ to write and suits small lists, though it is slow on long lists.