C++ Fibonacci, Sorting, and Binary Search Programs

Program Design Practice

A collection of C++ programs is useful only when each exercise teaches a transferable decision. Before coding, state the input domain, ownership of resources, algorithmic cost, and behavior for invalid input. Then compile with strong warnings and test boundaries rather than accepting one sample output.

Fibonacci with an Overflow Boundary

Check before addition so the program stops instead of overflowing an unsigned integer.

Print representable Fibonacci values

#include <iostream>
#include <limits>

int main() {
    unsigned long long a = 0, b = 1;
    for (int count = 0; count < 10; ++count) {
        std::cout << a << (count == 9 ? '\n' : ' ');
        if (b > std::numeric_limits<unsigned long long>::max() - a) break;
        const auto next = a + b;
        a = b; b = next;
    }
}

Output

0 1 1 2 3 5 8 13 21 34

Sort Before Binary Search

std::sort orders a random-access range. std::binary_search answers existence; lower_bound returns the first insertion position and is better when the index or duplicate range matters.

Use standard algorithms for production unless implementing the algorithm is the learning objective.
Search with the same ordering relation used to sort.
Choose a numeric type from the required Fibonacci range.

Sort, search, and report a position

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{9, 2, 7, 2, 5};
    std::sort(values.begin(), values.end());
    const int target = 7;
    const auto found = std::lower_bound(values.begin(), values.end(), target);
    if (found != values.end() && *found == target)
        std::cout << "index " << std::distance(values.begin(), found) << '\n';
}

Output

index 3

Verification Strategy

For numeric programs, test zero, negative values when allowed, and values near the chosen type’s limit. For containers, test empty and one-element cases before typical data. For text, decide whether bytes or Unicode code points are the intended unit instead of silently assuming ASCII.

Separate input/output from the core calculation so the algorithm can be tested without console redirection. Prefer standard algorithms and containers when they express the operation accurately, and explain complexity when input size changes whether the solution remains practical.

Before you move on

Algorithm Review

5 checks

Preconditions are stated.
Empty and duplicate inputs are tested.
Overflow is considered before arithmetic.
Complexity matches expected input size.
The output is verified independently.

Program Questions

Integer overflow eventually wraps or becomes undefined, depending on the type. Check the numeric limit before adding the next terms.

The searched range must be sorted with the same ordering used by the search.

Use empty, sorted, reversed, duplicate, and negative inputs, then verify no value was lost or duplicated.

Previous Next

C++ Fibonacci, Sorting, and Binary Search Programs

Program Design Practice

Fibonacci with an Overflow Boundary

Print representable Fibonacci values

Sort Before Binary Search

Sort, search, and report a position

Verification Strategy

Algorithm Review

Important Programs Connections

Program Questions

Why can a correct Fibonacci loop still produce wrong results?

What must be true before binary search runs?

How should a sorting program be tested?

C++ Programs Resources

Popular Tutorials