# Insertion Sort

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;

Example:

n = e7;

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