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

// Recursive binary search
//
// Binary search requires a sorted array.
//
// The central idea is:
//
//     Look at the middle entry.
//
// If that entry is the value we are searching for:
//
//     we are finished.
//
// If the value is smaller than the middle entry:
//
//     recursively search the left half.
//
// If the value is larger than the middle entry:
//
//     recursively search the right half.
//
// Thus, each recursive call reduces the size of the
// problem by approximately one half:
//
//     n
//
//     n/2
//
//     n/4
//
//     n/8
//
//     ...
//
// This should immediately remind us of the
// recurrence:
//
//     T(n) = T(n/2) + Theta(1),
//
// which gives:
//
//     T(n) = Theta(log(n)).
//
//
//
// We will represent the portion of the array being
// searched using a half-open interval:
//
//     [lower, upper)
//
// This means:
//
//     lower
//
// is the index of the first entry that may still
// contain the value, while:
//
//     upper
//
// is one position beyond the last entry that may
// contain the value.
//
// Thus:
//
//     [0, capacity)
//
// represents the entire array.
//
// The interval is empty precisely when:
//
//     lower == upper.
//
// This gives us a particularly clean trivial case
// for the recursion.

// Function declarations
int main();

std::size_t binary_search(
    double      const array[],
    std::size_t const capacity,
    double      const value
);

std::size_t binary_search_recursive(
    double      const array[],
    std::size_t const capacity,
    double      const value,
    std::size_t const lower,
    std::size_t const upper
);

std::size_t is_sorted(
    double      const array[],
    std::size_t const capacity
);


// Function definitions
int main() {
    // A sorted array.

    std::size_t const N{ 10 };

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

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


    // Search for the integer values from 0 through
    // 10.
    //
    // The int n is converted to a double when
    // binary_search() is called.

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

        if ( position == N ) {
            std::cout << n << " not found"
                      << std::endl;
        } else {
            // Similarly, n is converted to a
            // double before this comparison.

            assert( data[position] == n );

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


    // Search for every value that actually occurs
    // in the array.

    for ( std::size_t k{ 0 }; k < N; ++k ) {
        assert(
            binary_search( data, N, data[k] )
            == k
        );
    }


    // Test values smaller than and larger than all
    // entries in the array.

    assert(
        binary_search( data, N, -100.0 )
        == N
    );

    assert(
        binary_search( data, N, 100.0 )
        == N
    );


    // A one-entry array.

    double single[1]{ 42.0 };

    assert(
        binary_search( single, 1, 42.0 )
        == 0
    );

    assert(
        binary_search( single, 1, 17.0 )
        == 1
    );


    // An empty array contains no values.

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


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

    return 0;
}


// std::size_t binary_search( ... )
//
// @author    Douglas Wilhelm Harder
// @date      2020-11-01
// @version   2.0
//
// @param array
//     A sorted array of double values to be
//     searched.
//
// @param capacity
//     The number of entries in the array.
//
// @param value
//     The value for which we are searching.
//
// @returns
//     If value is found, return an index at which
//     it occurs.
//
//     If value is not found, return capacity.
//
// @precondition
//     The array must be sorted into nondecreasing
//     order.
//
//     If capacity is greater than zero, array must
//     point to an array containing at least
//     capacity entries.
//
// @algorithm
//
// Verify that the array is sorted and then call a
// recursive helper to search the half-open interval:
//
//     [0, capacity).
//
// The helper keeps all indices relative to the
// ORIGINAL array.
//
// This avoids having to translate indices returned
// from recursive searches of subarrays.

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

    assert(
        is_sorted( array, capacity )
        == capacity
    );

    return binary_search_recursive(
        array,
        capacity,
        value,
        0,
        capacity
    );
}


// std::size_t binary_search_recursive( ... )
//
// @param array
//     The complete sorted array.
//
// @param capacity
//     The number of entries in the complete array.
//
// @param value
//     The value for which we are searching.
//
// @param lower
//     The first index that may still contain value.
//
// @param upper
//     One position beyond the final index that may
//     still contain value.
//
// @returns
//     If value is found, return its index in the
//     ORIGINAL array.
//
//     If value is not found, return capacity.
//
// @precondition
//
//     0 <= lower <= upper <= capacity.
//
// @algorithm
//
// We are searching:
//
//     [lower, upper).
//
// If:
//
//     lower == upper,
//
// there are no entries left to search.
//
// Otherwise, examine the middle entry.
//
// If it equals value, return its index.
//
// If value is smaller, recursively search:
//
//     [lower, middle).
//
// If value is larger, recursively search:
//
//     [middle + 1, upper).

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

    if ( lower == upper ) {
        return capacity;
    }

    std::size_t const middle{
        lower + (upper - lower)/2
    };

    if ( array[middle] == value ) {
        return middle;
    } else if ( value < array[middle] ) {
        return binary_search_recursive(
            array,
            capacity,
            value,
            lower,
            middle
        );
    } else {
        return binary_search_recursive(
            array,
            capacity,
            value,
            middle + 1,
            upper
        );
    }
}


// std::size_t is_sorted( ... )
//
// @author    Douglas Wilhelm Harder
// @date      2020-09-09
// @version   1.1
//
// @param array
//     An array of double values to be checked.
//
// @param capacity
//     The number of entries in the array.
//
// @returns
//     If the array is sorted:
//
//         capacity
//
//     is returned.
//
//     Otherwise, the first index k for which:
//
//         array[k] < array[k - 1]
//
//     is returned.
//
// @definition
//
// An array is sorted into nondecreasing order if:
//
//     array[i] <= array[j]
//
// whenever:
//
//     i <= j.
//
// Thus, repeated values are allowed.
//
// @algorithm
//
// Beginning at index 1, compare each entry with
// its predecessor.
//
// If:
//
//     array[k] < array[k - 1],
//
// return k.
//
// If no such index exists, return capacity.
//
// Empty arrays and arrays containing one entry are
// automatically sorted.

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

    for ( std::size_t k{ 1 };
          k < capacity;
          ++k ) {
        if ( array[k] < array[k - 1] ) {
            return k;
        }
    }

    return capacity;
}














































// Understanding the recursion
//
// Consider the sorted array:
//
//     index:   0   1   2   3   4   5   6   7
//
//     value:   2   5   8  12  16  23  38  41
//
// Suppose we search for:
//
//     23.
//
// Initially, the search interval is:
//
//     [0, 8).
//
// This contains all eight entries:
//
//     [ 2  5  8  12  16  23  38  41 ]
//
//
//
// The middle index is:
//
//     0 + (8 - 0)/2
//
//       = 4.
//
// Thus, we examine:
//
//     array[4] = 16.
//
// Since:
//
//     23 > 16,
//
// the value cannot occur at indices:
//
//     0, 1, 2, 3, or 4.
//
// We therefore recursively search:
//
//     [5, 8).
//
//
//
// The remaining entries are:
//
//     [ 23  38  41 ]
//
//       ^
//       |
//     index 5
//
// The middle index is:
//
//     5 + (8 - 5)/2
//
//       = 6.
//
// Thus:
//
//     array[6] = 38.
//
// Since:
//
//     23 < 38,
//
// we recursively search:
//
//     [5, 6).
//
//
//
// There is now only one possible entry:
//
//     array[5] = 23.
//
// We have found the value and return:
//
//     5.
//
//
//
// The recursive calls were:
//
//     search [0, 8)
//
//         search [5, 8)
//
//             search [5, 6)
//
//                 found at index 5.
//
//
//
// Now suppose we search for:
//
//     22.
//
// We begin:
//
//     [0, 8)
//
// and examine:
//
//     16.
//
// Since:
//
//     22 > 16,
//
// search:
//
//     [5, 8).
//
// We examine:
//
//     38.
//
// Since:
//
//     22 < 38,
//
// search:
//
//     [5, 6).
//
// We examine:
//
//     23.
//
// Since:
//
//     22 < 23,
//
// search:
//
//     [5, 5).
//
// But:
//
//     [5, 5)
//
// contains no entries.
//
// Therefore, the value is not present.
//
// We return:
//
//     capacity.
//
//
//
// Why use [lower, upper)?
//
// There are several ways to represent the portion
// of an array being searched.
//
// We could use two inclusive indices:
//
//     [lower, upper]
//
// or we could use:
//
//     [lower, upper).
//
// The second convention has several useful
// properties.
//
//
//
// First:
//
//     [0, capacity)
//
// represents the entire array naturally.
//
//
//
// Second, the number of entries in:
//
//     [lower, upper)
//
// is simply:
//
//     upper - lower.
//
//
//
// Third, the interval is empty exactly when:
//
//     lower == upper.
//
//
//
// Fourth, splitting around middle is clean:
//
//     left:
//
//         [lower, middle)
//
//     middle:
//
//         array[middle]
//
//     right:
//
//         [middle + 1, upper).
//
//
//
// This is the same half-open interval convention
// commonly used by loops:
//
//     for ( std::size_t k{ lower };
//           k < upper;
//           ++k ) {
//
//         ...
//     }
//
//
//
// Why calculate the middle this way?
//
// We use:
//
//     lower + (upper - lower)/2
//
// rather than:
//
//     (lower + upper)/2.
//
// Mathematically, these expressions give the same
// result when using integer arithmetic.
//
// Computationally, however:
//
//     lower + upper
//
// could overflow if both indices were extremely
// large.
//
// The expression:
//
//     upper - lower
//
// cannot exceed the size of the interval.
//
// Therefore:
//
//     lower + (upper - lower)/2
//
// is the safer standard calculation.
//
//
//
// The trivial case
//
// Earlier recursive functions often had trivial
// cases such as:
//
//     n == 0
//
// or:
//
//     n <= 1.
//
// Here, the problem is represented by an interval.
//
// The trivial case is:
//
//     lower == upper.
//
// This means:
//
//     number of entries
//
//       = upper - lower
//
//       = 0.
//
// There is nothing left to search.
//
// Therefore, the value is not present.
//
//
//
// Notice that an interval containing ONE entry is
// not a special case.
//
// Suppose:
//
//     upper = lower + 1.
//
// Then:
//
//     middle
//
//       = lower + (upper - lower)/2
//
//       = lower + 1/2
//
//       = lower.
//
// We examine that one entry.
//
// If it matches, we return its index.
//
// If it does not match, the next recursive call is
// an empty interval.
//
// Thus, there is no need for a separate:
//
//     capacity <= 2
//
// linear-search case.
//
// The ordinary recursive rule already handles one
// or two entries correctly.
//
//
//
// Why does binary search require a sorted array?
//
// Suppose:
//
//     value < array[middle].
//
// Because the array is sorted, every entry to the
// right satisfies:
//
//     array[k] >= array[middle].
//
// Therefore:
//
//     array[k] > value.
//
// None of those entries can equal value.
//
// We can safely discard that entire half.
//
// Similarly, if:
//
//     value > array[middle],
//
// every entry to the left of and including middle
// can be discarded.
//
// Without the sorted-array precondition, neither
// conclusion would be valid.
//
//
//
// How quickly does the problem shrink?
//
// Suppose we begin with approximately:
//
//     1 000 000
//
// entries.
//
// Successive recursive calls search approximately:
//
//     1 000 000
//
//       500 000
//
//       250 000
//
//       125 000
//
//        62 500
//
//        31 250
//
//        15 625
//
//         7 812
//
//         3 906
//
//         1 953
//
//           976
//
//           488
//
//           244
//
//           122
//
//            61
//
//            30
//
//            15
//
//             7
//
//             3
//
//             1.
//
// Thus, only about twenty recursive steps are
// required.
//
// This is the power of repeatedly dividing the
// problem size rather than reducing it by one.
//
//
//
// The recurrence
//
// Let T(n) represent the work required to search n
// entries.
//
// At each call:
//
//     1. calculate the middle index,
//
//     2. examine the middle entry,
//
//     3. recursively search at most half of the
//        remaining array.
//
// Thus:
//
//     T(n) = T(n/2) + Theta(1).
//
// We have already studied this recurrence.
//
// Its solution is:
//
//     T(n) = Theta(log(n)).
//
// More precisely, the logarithm is base 2, but in
// asymptotic notation the base of the logarithm
// changes only a constant factor.
//
//
//
// Compare with linear search
//
// A linear search examines entries one after
// another:
//
//     0, 1, 2, 3, 4, ...
//
// In the worst case, it may examine all n entries.
//
// Thus:
//
//     linear search:
//
//         Theta(n)
//
//     binary search:
//
//         Theta(log(n)).
//
//
//
// For:
//
//     n = 1 000 000,
//
// a linear search may require approximately:
//
//     1 000 000
//
// comparisons.
//
// Binary search requires only approximately:
//
//     20.
//
// This enormous improvement is possible because the
// sorted order allows us to eliminate approximately
// half of the remaining entries after each
// comparison.
//
//
//
// Compare with print_binary()
//
// The recursive binary-printing function had the
// structure:
//
//     print_binary( n/2 )
//
// and therefore:
//
//     T(n) = T(n/2) + Theta(1).
//
// Recursive binary search has the same mathematical
// structure.
//
// In one case, we divide an integer by two.
//
// In the other, we divide a search interval
// approximately in half.
//
// The applications are quite different, but the
// recurrence is the same:
//
//     T(n) = T(n/2) + Theta(1)
//
// and therefore both have:
//
//     Theta(log(n))
//
// recursive depth.
//
//
//
// Compare with recursive selection sort
//
// Recursive selection sort reduced:
//
//     n
//
// to:
//
//     n - 1.
//
// Its recursive calls looked like:
//
//     n
//
//     n - 1
//
//     n - 2
//
//     n - 3
//
//     ...
//
// giving:
//
//     Theta(n)
//
// levels of recursion.
//
// Binary search instead produces:
//
//     n
//
//     n/2
//
//     n/4
//
//     n/8
//
//     ...
//
// giving:
//
//     Theta(log(n))
//
// levels.
//
// The way the problem size changes between
// recursive calls is therefore crucial.
//
//
//
// Stack space
//
// Since binary search has:
//
//     Theta(log(n))
//
// recursive calls active at once, recursive binary
// search requires:
//
//     Theta(log(n))
//
// additional stack space.
//
// The iterative binary search performs the same
// search using only a few index variables and
// therefore requires:
//
//     Theta(1)
//
// additional space.
//
// Thus, recursion does not make binary search
// asymptotically faster.
//
// Both versions have:
//
//     Theta(log(n))
//
// runtime.
//
// The recursive version simply expresses the
// divide-and-conquer structure directly.
//
//
//
// A subtle issue with the assertion
//
// The public binary_search() function contains:
//
//     assert(
//         is_sorted( array, capacity )
//         == capacity
//     );
//
// This is useful because binary search is correct
// only if the array is sorted.
//
// However, checking whether the array is sorted
// requires:
//
//     Theta(n)
//
// time.
//
// Thus, in a debug build, the complete function as
// written actually performs:
//
//     Theta(n)
//
// work before beginning its:
//
//     Theta(log(n))
//
// binary search.
//
// Therefore, if we include the assertion in our
// runtime measurement:
//
//     Theta(n) + Theta(log(n))
//
//       = Theta(n).
//
// This does NOT mean that binary search itself is
// linear.
//
// It means that our debugging check is more
// expensive than the algorithm being checked.
//
// When:
//
//     NDEBUG
//
// is defined, assert() expressions disappear and
// the search itself has the expected:
//
//     Theta(log(n))
//
// runtime.
//
//
//
// Repeated values
//
// Our definition of sorted allows repeated values.
//
// For example:
//
//     [ 1  2  2  2  5 ]
//
// is sorted.
//
// If we search for:
//
//     2,
//
// this implementation returns:
//
//     an index at which 2 occurs.
//
// It does NOT promise to return:
//
//     the first occurrence
//
// or:
//
//     the last occurrence.
//
// Finding specifically the first or last occurrence
// requires a modified binary-search algorithm.
//
//
//
// Floating-point values
//
// This exercise searches an array of double values
// using:
//
//     ==.
//
// That is acceptable for the particular values in
// these tests because we are searching for values
// already stored in the array or exactly
// representable integer values.
//
// In general, however, calculations involving
// floating-point values may introduce rounding
// error.
//
// Consequently, searching for the result of a
// floating-point calculation using exact equality
// may not always produce the result one expects.
//
// That is a separate issue from binary search
// itself.
//
//
//
// Questions:
//
// 1. What precondition must hold before binary
//    search can be used?
//
// 2. What does the half-open interval:
//
//        [lower, upper)
//
//    represent?
//
// 3. How many entries are contained in that
//    interval?
//
// 4. What condition tells us that the interval is
//    empty?
//
// 5. Why is an empty interval the natural trivial
//    case?
//
// 6. Why do we not require a separate trivial case
//    for an interval containing one entry?
//
// 7. Why do we calculate the middle index as:
//
//        lower + (upper - lower)/2
//
//    rather than:
//
//        (lower + upper)/2?
//
// 8. If value is less than array[middle], why can
//    the entire right half be discarded?
//
// 9. If value is greater than array[middle], why
//    can the entire left half, including middle,
//    be discarded?
//
// 10. Trace the recursive calls when searching for
//     23 in:
//
//        [ 2  5  8  12  16  23  38  41 ].
//
// 11. Trace the recursive calls when searching for
//     22 in the same array.
//
// 12. What recurrence describes the runtime of
//     recursive binary search?
//
// 13. Why does that recurrence give:
//
//        Theta(log(n))?
//
// 14. Approximately how many times can an array of
//     one million entries be divided in half before
//     only one entry remains?
//
// 15. Compare the worst-case runtimes of linear
//     search and binary search.
//
// 16. Why can binary search be dramatically faster
//     than linear search?
//
// 17. How does the recursion in binary search
//     compare with the recursion in print_binary()?
//
// 18. How does it compare with recursive selection
//     sort?
//
// 19. What additional stack space does recursive
//     binary search require?
//
// 20. Why does the is_sorted() assertion make the
//     complete function Theta(n) in a debug build?
//
// 21. If the array contains repeated values, does
//     this function necessarily return the first
//     occurrence?
//
// 22. What potential issue arises when searching
//     calculated floating-point values using exact
//     equality?
//
//
//
// The central recursive question is:
//
//     If I examine the middle entry, can I determine
//     which smaller version of the SAME problem
//     still needs to be solved?
//
// Because the array is sorted, the answer is yes.
//
// We can discard approximately half of the problem
// after every comparison.
//
// This gives binary search its characteristic
// recurrence:
//
//     T(n) = T(n/2) + Theta(1)
//
// and its:
//
//     Theta(log(n))
//
// runtime.
//
// This is one of the clearest examples of how the
// choice of a smaller recursive problem can
// determine the efficiency of an algorithm.