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

/**
 * Search for value x in given array of N elements
 *
 * Return the index at which the element can be found,
 * or -1 if the element was not found.
 */
int binary_search(int x, int* array, int N) {
    if (N == 0) return -1;

    // Search space is [lo..hi)
    int lo = 0, hi = N;
    while (lo + 1 < hi) {
        int h = (hi + lo) / 2;
        if (array[h] <= x) lo = h;
        if (array[h] > x)  hi = h;
    }

    return array[lo] == x ? lo : -1;
}

// [3..5)
// h = 4

int main() {
    int N = 8;
    int array[] = { 1, 3, 4, 4, 7, 10, 13, 20 };

    printf("15: %d\n",  binary_search(15, array, N));
    printf("4: %d\n",   binary_search(4,  array, N));
    printf("1: %d\n",   binary_search(1,  array, N));
    printf("20: %d\n",  binary_search(20, array, N));

    return 0;
}