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

void genarray (int A[], int n)
{
    int i;

    A[0] = rand() % 10;
    for (i=1; i<n; ++i) {
        if (rand() % 3) A[i] = A[i-1];
        else A[i] = A[i-1] + rand() % 5;
    }
}

void prnarray ( int A[], int n )
{
    int i;

    for (i=0; i<n; ++i) printf("%3d ", A[i]);
    printf("\n");
}

/* Finding the first match (if any) */
int binsearch ( int A[], int n, int x )
{
    int L, R, M;

    if (x == A[0]) return 0;
    if (x < A[0]) return -1;
    L = 1;
    if (x > A[n-1]) return -1;
    R = n-1;
    while (L < R) {
        M = (L + R) / 2;
        if (x <= A[M]) R = M;
        else L = M + 1;
    }
    if (x == A[L]) return L;
    return -1;
}

int main ()
{
    int A[100], n = 100, x, r;

    srand((unsigned int)time(NULL));
    genarray(A,n);
    prnarray(A,n);
    printf("x = "); scanf("%d", &x);
    r = binsearch(A,n,x);
    printf("r = %d\n", r);
    exit(0);
}