#include <cstddef>
#include <iostream>

/***************************************************
 * Finding the first occurrence in a sorted array
 *
 * An array is indexed from 0 through capacity - 1,
 * whatever its capacity.
 *
 * An array a is sorted if
 *
 *     a_0 <= a_1 <= a_2 <= ...
 *         <= a_(capacity - 2)
 *         <= a_(capacity - 1).
 *
 * The subscripts above use the notation of a
 * sequence, such as you might see in calculus.
 *
 * In C++, this condition would be written as
 *
 *     a[0] <= a[1]
 *     a[1] <= a[2]
 *     a[2] <= a[3]
 *     ...
 *     a[capacity - 2] <= a[capacity - 1].
 *
 * In some cases, the arrays we are working with
 * are already sorted. We can take advantage of
 * this ordering to avoid unnecessary comparisons.
 ***************************************************/

// Function declarations
std::size_t first_in_sorted_array(
    int const n,
    int const array[],
    std::size_t const capacity
);

int main();

// Function definitions
int main() {
    int array1[8]{
        15, 34, 40, 42, 59, 65, 69, 80
    };

    int array2[27]{
         2,  3, 17, 19, 22, 23, 29, 34, 38,
        38, 44, 46, 46, 46, 48, 50, 52, 57,
        65, 69, 73, 79, 88, 88, 93, 98, 99
    };

    for ( int k{ 0 }; k < 100; ++k ) {
        std::size_t const index{
            first_in_sorted_array( k, array1, 8 )
        };

        if ( index != 8 ) {
            std::cout << k << ": " << index
                      << std::endl;
        }
    }

    std::cout << std::endl;

    for ( int k{ 0 }; k < 100; ++k ) {
        std::size_t const index{
            first_in_sorted_array( k, array2, 27 )
        };

        if ( index != 27 ) {
            std::cout << k << ": " << index
                      << std::endl;
        }
    }

    return 0;
}

/***************************************************
 * first_in_sorted_array
 *
 * Return the index of the first occurrence of n in
 * the sorted array.
 *
 * If n does not appear in the array, return
 * capacity.
 ***************************************************/
std::size_t first_in_sorted_array(
    int const n,
    int const array[],
    std::size_t const capacity
) {
    for ( std::size_t k{ 0 }; k < capacity; ++k ) {
        if ( array[k] == n ) {
            return k;
        }
    }

    return capacity;
}




































// Hint:
//
// The function above works, but it does not take
// advantage of the fact that the array is sorted.
//
// Suppose you are searching for 42 and encounter
// an entry containing 43.
//
// Because the array is sorted, could 42 possibly
// occur anywhere after that entry?
//
// As you step through the array, there are three
// possibilities:
//
//     array[k] < n
//     array[k] == n
//     array[k] > n
//
// Think about what you should do in each case.
//
// Your function should still return the index of
// the first occurrence of n if it is found, and
// capacity if n is not found.




































// One solution:

/*
std::size_t first_in_sorted_array(
    int const n,
    int const array[],
    std::size_t const capacity
) {
    for ( std::size_t k{ 0 }; k < capacity; ++k ) {
        if ( array[k] == n ) {
            return k;
        } else if ( array[k] > n ) {
            return capacity;
        }
    }

    return capacity;
}
*/