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;

TargetStartEndMiddle
n08(Start+End) / 2 = Middle

Arraye1e2e3e4e5e6e7e8e9
Index012345678

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.
TargetStartEndMiddle
n28(Start+End) / 2 = Middle = 5(index 5)

Arraye1e2e3e4e5e6e7e8e9
Index012345678