#include <cassert>
#include <cstddef>
#include <iostream>

// Finding an entry in an array
//
// Suppose you are given an array of numbers
// and asked to find a particular value.
//
// The simplest approach is to examine the
// entries one at a time, starting at index 0.
//
// As soon as the value is found, return
// its index.
//
// If the value does not occur in the array,
// return capacity.
//
// Since the valid indices are
//
//     0, 1, ..., capacity - 1,
//
// returning capacity unambiguously indicates
// that the value was not found.
//
// This algorithm is called a linear search.
//
// If a value appears more than once, the
// function must return its first occurrence.
//
// An array with capacity zero contains no
// elements, so the function must return 0.
//
// After implementing and testing this
// function, we will investigate how the
// amount of work changes as the array grows.

// Function declarations
std::size_t find(
    double      const array[],
    std::size_t const capacity,
    double      const value
);

int main();

// Function definitions
int main() {
    std::size_t const N{ 10 };

    double data[N]{
        4.0, 1.9, 0.2, 8.0, 4.3,
        8.4, 4.1, 9.9, 3.9, 6.8
    };

    std::cout << "Starting testing"
              << std::endl;

    // Search for the integers from 0 through 10.
    //
    // Each integer is converted to double
    // when passed to find(...).

    for ( int n{ 0 }; n <= 10; ++n ) {
        std::size_t const posn{
            find( data, N, n )
        };

        if ( posn == N ) {
            std::cout << n << " not found"
                      << std::endl;
        } else {
            assert( posn < N );
            assert( data[posn] == n );

            std::cout << n
                      << " found at position "
                      << posn << std::endl;
        }
    }

    // Additional tests:
    //
    // Find the first and last entries,
    // and search for a value that is absent.

    assert( find( data, N, 4.0 ) == 0 );
    assert( find( data, N, 6.8 ) == N - 1 );
    assert( find( data, N, 5.0 ) == N );

    // If a value occurs more than once,
    // return its first occurrence.

    double repeated[5]{
        3.0, 7.0, 2.0, 7.0, 9.0
    };

    assert( find( repeated, 5, 7.0 ) == 1 );

    // An empty array has no valid indices.
    // Passing nullptr with capacity zero
    // is permitted because no elements
    // will be accessed.

    assert( find( nullptr, 0, 42.0 ) == 0 );

    std::cout << "Finished testing"
              << std::endl;

    return 0;
}

// std::size_t find( ... )
//
// @author    Douglas Wilhelm Harder
// @date      2020-09-09
//
// @param array
//     The array of doubles to be searched.
//
// @param capacity
//     The number of entries in the array.
//
// @param value
//     The value to search for.
//
// @returns
//     The first index at which value occurs,
//     or capacity if the value is not found.
//
// @algorithm
//     Perform a linear search, examining
//     entries from index 0 onward.
//
//     Return immediately when the value
//     is found. If every entry has been
//     examined without finding the value,
//     return capacity.
//
// @precondition
//     If capacity is greater than zero,
//     array must point to at least
//     capacity valid doubles.

std::size_t find(
    double      const array[],
    std::size_t const capacity,
    double      const value
) {
    assert( (capacity == 0) || (array != nullptr) );

    for ( std::size_t k{ 0 };
          k < capacity;
          ++k ) {
        if ( array[k] == value ) {
            return k;
        }
    }

    return capacity;
}




































// Questions:
//
// 1. What happens if the value is stored
//    at index 0?
//
// 2. What happens if the value is stored
//    at the last index?
//
// 3. What happens if the value does not
//    occur in the array?
//
// 4. If the value occurs at several
//    indices, which index is returned?
//
// 5. Why do we return capacity rather
//    than -1 when the value is absent?
//
// 6. Is the function safe to call with
//    capacity zero?
//
// 7. Why is the array parameter const?
//
// 8. What is the maximum number of
//    comparisons with value that this
//    function might perform?




































// Answers:
//
// 1. The function returns 0 after
//    examining only the first entry.
//
// 2. The function examines every entry
//    before returning capacity - 1.
//
// 3. The function examines every entry
//    and returns capacity.
//
// 4. It returns the smallest index
//    at which the value occurs.
//
// 5. The return type is std::size_t,
//    which is an unsigned integer type.
//
//    Moreover, capacity is immediately
//    recognizable as an invalid index.
//
// 6. Yes. The loop is skipped, and the
//    function returns zero without
//    accessing the array.
//
// 7. Searching should not modify
//    the contents of the array.
//
// 8. At most capacity comparisons
//    with value are performed.









// From linear search to asymptotic runtime
//
// Consider an array containing 10 numbers. If the
// number we want is the first entry, we find it
// immediately. If it is the last entry, we must
// examine all 10 entries. If it is absent, we must
// also examine all 10 entries before we can conclude
// that it is not there.
//
// Now suppose the array contains 100 numbers, or
// 1000, or one million. How much more work might
// the search require?
//
//
// 1. Counting the work
//
// Instead of measuring how many seconds a program
// takes on a particular computer, we can count an
// operation that represents its work.
//
// For linear search, a natural choice is the
// comparison
//
//     array[k] == value
//
// Suppose the array has capacity n.
//
//     Situation                 Comparisons
//     --------------------------------------
//     Value is first entry             1
//     Value is at index k          k + 1
//     Value is last entry              n
//     Value is absent                  n
//
// For an unsuccessful search, doubling the capacity
// doubles the number of comparisons. Increasing the
// capacity tenfold increases the number of comparisons
// tenfold.
//
// We are counting comparisons between array entries
// and the target value, not every machine instruction.
//
//
// 2. What happens as the array gets larger?
//
// When we analyze an algorithm, we are often less
// interested in the exact number of operations for
// one particular array and more interested in how
// the number of operations grows as the input becomes
// larger.
//
// This is the idea behind asymptotic runtime.
//
// For example, suppose one algorithm requires
//
//     n
//
// operations and another requires
//
//     3*n + 5
//
// operations.
//
// The second performs more operations under this
// simplified model, but both grow proportionally
// to n.
//
// If the input becomes sufficiently large and then
// doubles, the amount of work performed by either
// algorithm approximately doubles.
//
// We describe this kind of growth as linear.
//
//
// 3. Big O notation
//
// We use Big O notation to describe an upper bound
// on how quickly the amount of work grows as the
// input becomes larger.
//
// For linear search, the worst case requires exactly
//
//     n
//
// comparisons with the target value.
//
// Thus, the worst-case runtime is
//
//     O(n).
//
// More precisely, the worst-case number of comparisons
// is also bounded below by a constant multiple of n,
// so we can describe the worst-case runtime as
//
//     Theta(n).
//
// If the value is the first entry, however, only one
// comparison is required, regardless of the capacity
// of the array.
//
// Thus, the best-case runtime is
//
//     O(1),
//
// which is called constant time.
//
//
// Questions:
//
// 1. If an array contains n entries and the value is
//    absent, how many comparisons are performed?
//
// 2. If the value occurs at index k, how many
//    comparisons are performed?
//
// 3. If the capacity of the array doubles, what
//    happens to the number of comparisons required
//    in the worst case?
//
// 4. Why do we describe the worst-case runtime as
//    linear?
//
// 5. Why is the best-case runtime O(1)?
//
// 6. Suppose one algorithm performs approximately n
//    operations and another performs approximately
//
//        3*n + 5
//
//    operations. Why can both still be described as
//    having linear runtime?
//
//
// Questions to consider before the next topic:
//
// 1. If you knew the array was sorted in increasing
//    order, could you stop searching before reaching
//    the end in some cases?
//
// 2. Could you devise a method that repeatedly
//    eliminates half of the remaining entries?
//
// 3. For an array containing one million sorted
//    numbers, approximately how many times could you
//    halve the number of candidates before only one
//    remained?
//
//
// These questions lead to binary search, an algorithm
// whose runtime grows much more slowly than linear
// search.
//
// The important distinction at this stage is that
// Big O is not a stopwatch measurement.
//
// It describes how an algorithm's resource
// requirements scale as the input grows. This allows
// us to compare algorithms without tying the analysis
// to a particular computer.