# Binary Search Algorithm

## Table of Contents

## 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

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

**Iteration #1**- Find the middle point of array (
`[0]`

to`[7]`

):`0 + ceil( (7 - 0) / 2 ) =`

**4** - Is there 1 element left?:
*No* - Check middle point against target:

?**3**<**4** - Yes, so partition left side:
`[0]`

→`[3]`

- Find the middle point of array (
**Iteration #2**- Find the middle point of array (
`[0]`

to`[3]`

):`0 + ceil( (3 - 0) / 2 ) =`

**2** - Is there 1 element left?:
*No* - Check middle point against target:

?**3**<**2** - No, so partition right side:
`[2]`

→`[3]`

- Find the middle point of array (
**Iteration #3**- Find the middle point of array (
`[2]`

to`[3]`

):`2 + ceil( (3 - 2) / 2 ) =`

**3** - Is there 1 element left?:
*No* - Check middle point against target:

?**3**<**3** - No, so partition right side:
`[3]`

→`[3]`

- Find the middle point of array (
**Iteration #4**- Find the middle point of array (
`[3]`

to`[3]`

):`3 + ceil( (3 - 3) / 2 ) =`

**3** - Is there 1 element left?:
*Yes* - Return
**3**== element

- Find the middle point of array (

My implementation uses the alternative '

ceiling' method when partitioning the halves and actual recursion instead of the more common`while`

loop.