#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

bool is_number_in_array(int n, int* numbers, size_t len) {
    if(len == 0) {
        return false;
    }
    else if(len == 1) {
        return (n == numbers[0] ? true : false);
    }
    else {
        size_t len_0 = (len + 1) / 2;
        size_t len_1 = len / 2;
        assert(len_0 + len_1 == len);
        int* numbers_0 = numbers;         // first subarray starts at same point as numbers
        int* numbers_1 = numbers + len_0; // second subarray starts right after first
        if(n < numbers_1[0]) {
            return is_number_in_array(n, numbers_0, len_0);  // RECURSIVE CALL <<<<<<<
        }
        else {
            return is_number_in_array(n, numbers_1, len_1);  // RECURSIVE CALL <<<<<<<
        }
    }
}

int main(int argc, char* argv[]) {
    int primes[] = { 2, 3, 5, 7, 11, 13, 17, 19 };
    int n = 7;
    size_t num_primes = sizeof primes / sizeof primes[0];  // ONLY use this for static array

    printf("%d %s prime", n, is_number_in_array(n, primes, num_primes) ? "is" : "is NOT");
    
    return EXIT_SUCCESS;
}
/* vim: set tabstop=4 shiftwidth=4 fileencoding=utf-8 noexpandtab: */