Binary Search Algorithm

Es
C99 Algorithm

Table of Contents

  1. 1. Algorithm
  2. 2. Example
  3. 3. Source code

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.

Binary search
Fig.1 Binary search

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 ([0] to [7]): 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: [0] → [3]
  • Iteration #2
    1. Find the middle point of array ([0] to [3]): 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: [2] → [3]
  • Iteration #3
    1. Find the middle point of array ([2] to [3]): 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: [3] → [3]
  • Iteration #4
    1. Find the middle point of array ([3] to [3]): 3 + ceil( (3 - 3) / 2 ) = 3
    2. Is there 1 element left?: Yes
    3. Return 3 == element
Example
Fig.2 Example

3. Source code

Github source code
C source