# Binary Search Algorithm

C99 Algorithm

## 1. Algorithm

The binary search algorithm is actually really quite simple. It has a O(log n) worst and average performance. For it to work, the source data must already be sorted.

The algorithm finds the middle point of the data and compares it with the target value. It then breaks apart the data at that middle point and does the same middle-sectioning steps to the half that may contain the target value recursively until there is only 1 element to check left.

## 2. Example

My implementation uses the alternative 'ceiling' method when partitioning the halves and actual recursion instead of the more common `while` loop.

The target value is '`3`' for this example. The steps are as follows:

.
• Iteration #1
1. Find the middle point of array (`` to ``): `0 + ceil( (7 - 0) / 2 ) = 4`
2. Is there 1 element left?: No
3. Check middle point against target: `3 < 4`?
4. Yes, so partition left side: ````
• Iteration #2
1. Find the middle point of array (`` to ``): `0 + ceil( (3 - 0) / 2 ) = 2`
2. Is there 1 element left?: No
3. Check middle point against target: `3 < 2`?
4. No, so partition right side: ````
• Iteration #3
1. Find the middle point of array (`` to ``): `2 + ceil( (3 - 2) / 2 ) = 3`
2. Is there 1 element left?: No
3. Check middle point against target: `3 < 3`?
4. No, so partition right side: ````
• Iteration #4
1. Find the middle point of array (`` to ``): `3 + ceil( (3 - 3) / 2 ) = 3`
2. Is there 1 element left?: Yes
3. Return `3 == element`