# What you’re looking for is always found in the last place you look

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.

## Proposition

For a given search method for a searchable item, that item will always be found in the last search.

### Definitions

- 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.

## Assumptions

- 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.

## Proof

### Claim

An item cannot be found in less than `s` searches using a given search method.

#### Proof of Claim

Proof by induction

Let `s` be the number of searches.

##### Base Case

Let `s` = 1.

By assumption 1, an item cannot be found in less than 1 search, so the base case holds.

##### Inductive Case

Assume a sequence `s` = `k` searches are in a search method. Since the search method is efficient, if the item were found in `k` – 1 searches, the `k`th search would not occur. Therefore, the item cannot be found in `k` – 1 searches of the search method. Recurse.

By induction, the item cannot be found in less than `s` searches using a given search method.

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 `n`th search, which is the last search.

Q.E.D.