# Searching

Still under **HEAVY** construction

Searching over a set (o similar structure) can be done in an iterative way, but it presents several problems:

- first of all, you need to know the depth

#### Binary search

Efficient for finding in an ordered list.

#### Exhaustive search

Exploring every possible combination from a set of choices or values.

Using recursion is a good way to do that exploration.

Applications: - producing all Permutations of a set - enumerating all possible names, words, etc. - combinatorics and logic programming - Chess game (evaluate up to some depth or all possible movements in a given moment)

**Pseudo-code:**

```
Search(decisions):
- if there are no more decisions to make: Stop.
- else, let's handle one decision ourselves, and the rest by recursion
for each available choice 'C' for this decision:
- **Choose** 'C'.
- **Search** the remaining decisions that could follow 'C'.
```

Often, the search space consists of many decisions, each of which has several available choices. As an example, when enumerating all 5-letters strings, each of the 5 letters is a decision, and each of these 5 decisions have 26 possible choices. So, we **choose** one letter (this is the **decision**) and handover **recursively** the rest of decision (chooses).

As for recursion, a base case (the ideal or easy case) has to be thought, as well as the recursive pattern (the self-familiarity) of the problem.

#### Exhaustive search as a tree (of calls)

https://youtu.be/HvGkzDT2ffI?t=25m22s