I wanted to challenge myself to come up with a proof for the common saying that you always find what you’re looking for in the last place you look. Or you could claim I was bored, but you’ll need a proof for that.
For a given search method for a searchable item, that item will always be found in the last search.
- A look in a single place.
- Searchable Item
- An item that can be found within the limitations of the searcher.
- Search Method
- A sequence of searches. Every search method is consistent; that is, given a search item and method, the search method consists of the same sequence of searches each time it is invoked.
- A search item cannot be found in less than 1 search.
- The search does not end prematurely; that is, the item will always be found.
- The search method is capable of finding the item.
- The search method is efficient; that is, once the item is found, no further searches are conducted.
Let n be the number of searches in the given search method for the given item.
By the claim, the item cannot be found in n – 1 searches. Therefore, the item must be found on the nth search, which is the last search.