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

// Binary search
//
// Linear search examines the entries of an array
// one after another.
//
// If the array is sorted, however, we can do better.
//
// Binary search examines an entry near the middle of
// the portion of the array that could still contain
// the value.
//
// If the middle entry is too small, everything before
// it can also be eliminated.
//
// If the middle entry is too large, everything after
// it can also be eliminated.
//
// Thus, after each comparison, approximately half of
// the remaining entries can be eliminated.

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

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

int main();

// Function definitions
int main() {
    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 integers from 0 through 10.
    //
    // 'n' is converted to a double when
    // binary_search(...) is called.

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

        if ( posn == N ) {
            std::cout << n << " not found"
                      << std::endl;
        } else {
            // 'n' is converted to a double before
            // data[posn] and n are compared.

            assert( data[posn] == n );

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

    // Every entry in the array should be found.

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

    // Test an array containing one entry.

    double single[1]{ 42.0 };

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

    // Test an empty array.

    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-09-09
//
// @param array
//     A sorted array of doubles to be searched.
//
// @param capacity
//     The number of entries in the array.
//
// @param value
//     The value to search for.
//
// @returns
//     If value is found, the index at which it is
//     found is returned.
//
//     Otherwise, capacity is returned.
//
// @precondition
//     The array must be sorted in nondecreasing order.
//
// @algorithm
//     Maintain a range of indices in which the value
//     may still occur.
//
//     Examine an entry near the middle of that range.
//
//     If that entry equals value, return its index.
//
//     If that entry is less than value, eliminate it
//     and all entries before it.
//
//     Otherwise, eliminate it and all entries after it.
//
//     Continue until either the value is found or no
//     possible entries remain.
//
//     The range is represented as
//
//         [lower_index, upper_index)
//
//     so lower_index is included in the range while
//     upper_index is not.
//
//     Initially, the range is
//
//         [0, capacity)
//
//     containing every entry in the array.

std::size_t binary_search(
    double      const array[],
    std::size_t const capacity,
    double      const value
) {
    assert( is_sorted( array, capacity ) == capacity );

    std::size_t lower_index{ 0 };
    std::size_t upper_index{ capacity };

    while ( lower_index < upper_index ) {
        std::size_t const middle_index{
            lower_index
          + (upper_index - lower_index)/2
        };

        if ( array[middle_index] == value ) {
            return middle_index;
        } else if ( array[middle_index] < value ) {
            lower_index = middle_index + 1;
        } else {
            upper_index = middle_index;
        }
    }

    return capacity;
}


// std::size_t is_sorted( ... )
//
// @author    Douglas Wilhelm Harder
// @date      2020-09-09
//
// @param array
//     An array of doubles 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 at which an entry
//     is less than the previous entry is returned.
//
// @definition
//     An array is sorted if
//
//         array[i] <= array[j]
//
//     whenever
//
//         i <= j.
//
// @algorithm
//     Starting with index 1, compare each entry with
//     its predecessor.
//
//     As soon as an entry less than its predecessor
//     is found, return its index.
//
//     If every adjacent pair is in order, return
//     capacity.

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

    return capacity;
}
















































// Binary search: how does it work?
//
// Consider the following sorted array:
//
//     index:   0   1   2   3   4   5   6   7
//
//     value:   2   5   8  12  17  23  31  40
//
// Suppose we are searching for 31.
//
// Initially, every entry is a possibility:
//
//              possible
//              <----------------------------->
//
//     index:   0   1   2   3   4   5   6   7
//     value:   2   5   8  12  17  23  31  40
//
// We examine an entry near the middle:
//
//     index:   0   1   2   3   4   5   6   7
//     value:   2   5   8  12  17  23  31  40
//                             ^
//                            17
//
// Since
//
//     17 < 31,
//
// the desired value cannot be 17 or anything before
// it.
//
// We can therefore eliminate approximately half of
// the array:
//
//                             possible
//                             <--------------->
//
//     index:   0   1   2   3   4   5   6   7
//     value:   2   5   8  12  17  23  31  40
//                             X
//     discard: X   X   X   X   X
//
//
// We now examine the middle of what remains:
//
//     index:   0   1   2   3   4   5   6   7
//     value:   2   5   8  12  17  23  31  40
//                                     ^
//                                    31
//
// We have found the value.
//
//
// The important idea:
//
// Linear search eliminates one possibility at a time.
//
// Binary search eliminates approximately half of the
// remaining possibilities at a time.
//
//
//
// Runtime analysis
//
// Let us compare linear search and binary search.
//
// Suppose the value is not present in the array.
//
// With linear search, an array containing n entries
// may require n comparisons.
//
// For example:
//
//     capacity       linear-search comparisons
//     -----------------------------------------
//           10                    10
//          100                   100
//         1000                  1000
//      1000000               1000000
//
// Binary search behaves very differently.
//
// After each comparison, approximately half of the
// remaining entries can be eliminated.
//
// For example, starting with approximately one
// million entries:
//
//     1000000
//      500000
//      250000
//      125000
//       62500
//       31250
//       15625
//        7813
//        3907
//        1954
//         977
//         489
//         245
//         123
//          62
//          31
//          16
//           8
//           4
//           2
//           1
//
// It takes only about 20 halvings to reduce one
// million possibilities to approximately one.
//
// Compare:
//
//     Linear search:       about 1000000 comparisons
//
//     Binary search:       about      20 comparisons
//
// This is an enormous difference.
//
//
//
// Where does the logarithm come from?
//
// Suppose we repeatedly double the capacity:
//
//     capacity       maximum comparisons,
//                    approximately
//     ------------------------------------
//            1                1
//            2                2
//            4                3
//            8                4
//           16                5
//           32                6
//           64                7
//          128                8
//          256                9
//          512               10
//         1024               11
//
// Notice what happens.
//
// Every time the capacity doubles, binary search
// requires only about one additional comparison.
//
// We are therefore interested in the question:
//
//     How many times can we divide n by 2 before
//     reaching 1?
//
// Equivalently:
//
//     How many times must we multiply 1 by 2
//     before reaching n?
//
// This number is related to the base-2 logarithm:
//
//     log2(n)
//
// Thus, the worst-case runtime of binary search is
//
//     O(log(n)).
//
// More precisely, its worst-case runtime is
//
//     Theta(log(n)).
//
//
//
// Comparing growth rates
//
// Consider the following approximate amounts of work:
//
//     n             log2(n)          n
//     -----------------------------------------
//     10                 3.3             10
//     100                6.6            100
//     1000              10.0           1000
//     1000000           19.9        1000000
//     1000000000        29.9     1000000000
//
// The important observation is not the exact numbers.
//
// It is how slowly log2(n) grows.
//
// Increasing n from
//
//     1000
//
// to
//
//     1000000
//
// multiplies the size of the array by 1000.
//
// Linear search may therefore have 1000 times as
// much work.
//
// Binary search increases from approximately
//
//     10
//
// comparisons to approximately
//
//     20.
//
//
//
// Questions:
//
// 1. Why must the array be sorted before binary
//    search can be used?
//
// 2. If the middle entry is less than the desired
//    value, why can we eliminate everything before
//    the middle entry?
//
// 3. If the middle entry is greater than the desired
//    value, why can we eliminate everything after
//    the middle entry?
//
// 4. Approximately how many comparisons are required
//    to search an array containing 1024 entries?
//
// 5. Approximately how many comparisons are required
//    if the capacity doubles to 2048?
//
// 6. If the capacity increases from approximately
//    one thousand to approximately one million, why
//    does the number of comparisons only approximately
//    double?
//
// 7. What are the best-case and worst-case runtimes
//    of binary search?
//
//
//
// Answers:
//
// 1. The decision to discard half of the remaining
//    entries depends on the entries being ordered.
//
//    If the array is not sorted, discovering that
//
//        array[middle_index] < value
//
//    tells us nothing about whether value could occur
//    before middle_index.
//
//
// 2. Since the array is sorted, every entry before
//    middle_index is less than or equal to
//
//        array[middle_index].
//
//    If array[middle_index] is already less than the
//    desired value, all earlier entries must also be
//    too small.
//
//
// 3. Similarly, every later entry is greater than or
//    equal to array[middle_index].
//
//    If array[middle_index] is already greater than
//    the desired value, all later entries must also
//    be too large.
//
//
// 4. Since
//
//        1024 = 2^10,
//
//    approximately 10 comparisons are sufficient to
//    repeatedly halve the possibilities.
//
//    Depending on exactly how comparisons are counted
//    and whether the value is present, there can be
//    a small difference of one comparison.
//
//    The important observation is that the number is
//    approximately 10, not 1024.
//
//
// 5. Since
//
//        2048 = 2^11,
//
//    only about one additional comparison is needed.
//
//
// 6. Approximately:
//
//        1000       is close to 2^10,
//
//    while
//
//        1000000    is close to 2^20.
//
//    Thus, increasing the capacity by a factor of
//    approximately 1000 only doubles the number of
//    halvings from approximately 10 to approximately
//    20.
//
//
// 7. If the first middle entry examined contains the
//    desired value, only one comparison with an array
//    entry is required.
//
//    Thus, the best-case runtime is
//
//        O(1).
//
//    In the worst case, the number of remaining
//    possibilities is repeatedly divided by two.
//
//    Thus, the worst-case runtime is
//
//        O(log(n)).
//
//
//
// An important complication: the assertion
//
// At the beginning of binary_search(...) we wrote:
//
//     assert( is_sorted( array, capacity )
//             == capacity );
//
// Why?
//
// Binary search only works correctly if the array is
// sorted.
//
// During testing, the assertion helps us detect a
// violation of this requirement.
//
// There is, however, something interesting about its
// runtime.
//
// We just established that binary search requires
//
//     O(log(n))
//
// time in the worst case.
//
// But what is the worst-case runtime of
//
//     is_sorted( array, capacity )?
//
// It is
//
//     O(n).
//
// Thus, if assertions are enabled, every call to
// binary_search(...) first performs an O(n) check
// before performing the O(log(n)) binary search.
//
// The total work is therefore approximately
//
//     n + log2(n),
//
// rather than simply
//
//     log2(n).
//
// For large n, the n term dominates.
//
// Thus, with this assertion enabled, the runtime of
// the entire function call is
//
//     O(n).
//
// This does NOT mean that binary search itself is
// O(n).
//
// The binary-search algorithm is still O(log(n)).
//
// The additional O(n) work comes from checking its
// precondition.
//
//
//
// Why include the assertion, then?
//
// At this stage, the assertion is useful because it
// catches programming errors.
//
// It says:
//
//     "Binary search requires a sorted array.
//      During testing, verify that I was given one."
//
// Assertions are normally intended to help find bugs
// during development.
//
// If the program is compiled with NDEBUG defined,
// assert(...) expressions are removed.
//
// In such a build, is_sorted(...) is not called by
// this assertion, and the binary_search(...) function
// has its expected O(log(n)) runtime.
//
// This gives us an important programming lesson:
//
// Checking that a precondition is true can sometimes
// require more work than the algorithm that relies
// on that precondition.
//
//
//
// One final comparison
//
// Suppose we have a sorted array containing one
// million entries.
//
// If we perform ONE search:
//
//     checking sorted order:    about 1000000 comparisons
//     binary search:            about      20 comparisons
//
// Checking the precondition every time would clearly
// dominate the work.
//
// But suppose the array was sorted once and then we
// performed one million searches without modifying
// the array.
//
// We would not normally need to prove again before
// every search that the array was sorted.
//
// The fact that the array remains sorted is something
// the program can know from how the array is being
// used.
//
// This idea will become increasingly important:
//
//     What do we know to be true before an algorithm
//     begins?
//
// Such requirements are called preconditions.
//
// A good algorithm can often be much faster because
// it is allowed to take advantage of information
// supplied by its preconditions.