In binary search, the idea of the algorithm is to divide and conquer, reducing the search area by half each time, trying to find n.

- In order to leverage this power however, our array must first be sorted, else we can not make assumptions about the array’s contents.

Algorithm:

- Repeat until the (sub) Array is of size 0:

- calculate the middle point of the current (sub) Array.

- If the target is in the middle, stop.

- Else, if the target is less than what’s at the middle, repeat, changing the end point to be just to the left of the middle.

- Else, if the target is greater than what’s at the middle, repeat, changing the start point to be just the right of the middle.

Example:

n = **e5**;

Target | Start | End | Middle |

n | 0 | 8 | (Start+End) / 2 = Middle |

Array | e1 | e2 | e3 | e4 | e5 | e6 | e7 | e8 | e9 |

Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

Example:

n = **e7**;

- Check if (Middle = n) and if it is true, stop.
- Else, check if (The value of middle < n or > n)
- Repeat, the calculation to find middle: 6+8/2 = Middle = 7(index).
- Repeat the steps 1,2 and 3 until find n.

- Check if (Middle = n) and if it is true, stop.
- Else, check if (The value of middle < n or > n)
- Repeat, the calculation to find middle: 6+6/2 = Middle = 6(index).
- Repeat the steps 1,2 and 3 until find n.

Target | Start | End | Middle |

n | 2 | 8 | (Start+End) / 2 = Middle = 5(index 5) |

Array | e1 | e2 | e3 | e4 | e5 | e6 | e7 | e8 | e9 |

Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |