Binary search on a uniformly distributed vector I am trying to write a binary search using recursion in C on a sorted vector that we can assume comes from a uniform distribution between the start and end values. What I am trying to write is an algorithm that performs best in expected time. I am having some issue with picking the correct index to 'split' at and while it passes my tests, it feels a bit hacky.

int weighted_binary_split(int *x, int start_limit, int start_idx, int end_idx,
                          int val, int *depth) {
    // For a vector of length `n` with known starting and ending values,
    //     x[start_idx:end_idx+1] = [start, ..., end]
    // searches for `val` in `x`, assuming `x` is uniformly distributed and
    // ordered. Note that we always get the first occurence of `val` in `x`.
    // I say 'best' because it is simply intuition.
    // Note that when initially calling this, we will have
    //     start_limit = start_idx
    // however when we are within the recursion this is no longer the case.
    int n = end_idx - start_idx + 1;
    int start = x[start_idx];
    int end = x[end_idx];
    int out;
    int i;

    // Keep track of how many iterations/depth we have gone in binary search
    // tree.
    *depth += 1;

    // Catch the case where end == start (causing divide by 0 below).
    if (end - start == 0) {
        return start_idx;
    }

    // Catch the case where val == start (can just return start_idx).
    if (val == start) {
        return start_idx;
    }

    // We want to find
    //     (val - start)/((end - start)/n) = n*val/(end - start),
    // rounded to the nearest integer.
    // Note there is no point using
    //     1) idx = start_idx 
    //        as if val == x[start_idx] ==&gt; val == start, caught above.
    //     2) idx = start_idx + n = end_idx + 1, too big for vector.
    // Hence we use (n - 1). THIS PART FEELS HACKY.
    int idx = start_idx + ((n-1)*(val - start))/(end - start);
    if (idx == start_idx) {
        idx += 1;
    }

    if (x[idx] &gt; val) {
        // Search again with idx as the new `end_idx`.
        out = weighted_binary_split(x, start_limit, start_idx, idx, val, depth);
    } else if (x[idx] &lt; val) {
        // Search again with idx as the new `start_idx`.
        out = weighted_binary_split(x, start_limit, idx, end_idx, val, depth);
    } else {
        // In this case we have found val in x at x[idx].
        // We finally get the first occurence of `val` in x[start_limit:idx+1].
        for (i=1; i&lt;idx-start_limit+1; i++) {
            if (x[idx - i] != x[idx]) {
                // We have found our first value!
                return idx - i + 1;
            }
        }

        // If we reach this point, then x[start_limit] was the first value.
        return start_limit;
    }

    return out;
}


Below is a test template you can use.

int example_split() {
    // Test that our weighted binary split works correctly.
    int x[10] = {0, 1, 2, 2, 4, 5, 6, 6, 7, 9};
    int start_idx = 0;
    int end_idx = 9;
    int val = 2;
    int idx;
    int i;
    int depth = 0;

    idx = weighted_binary_split(x, start_idx, start_idx, end_idx, val, &amp;depth);
    printf("\nFirst index into:\n\tx = (");
    for (i=0; i&lt;10; i++) {
        printf("%d,", x[i]);
    }
    printf(")");
    printf("\nfor:\n\tval = %d", val);
    printf("\nis\n\tidx = %d", idx);
    printf("\nwith\n\tx[idx]=%d", x[idx]);
    printf("\nat\n\tdepth=%d\n", depth);

    return 0;
}
Bug
Generally code should prevent stack overflows from occurring. The search implemented here causes a stack overflow when the item searched for is not in the array. I tested the code using 8 as the value to search for which caused a recursive stack overflow.

I searched the internet for Weighted Binary Search and couldn't find it, instead I found Weighted Binary Tree.

Wikipedia defines a binary search as "In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. ..."

The search implemented is not a binary search. A binary search always divides the search area by two.

I'm not really sure why there is a for loop in the function weighted_binary_split(), it doesn't comply with a binary search.

Handling Errors
Since the code is keeping track of the depth of the search a possible solution to a stack overflow problem would be to check the value of depth against Log(N) where N is the number of items in the array. A secondary check might be to check the value of depth against N itself because N would be the limit in a linear search.

The function weighted_binary_split() could return -1 in the case of an error or use setjmp(jmp_buf env) and longjmp(jmp_buf env, int value) if negative values are valid in the search.

Always check for possible errors when developing code.

Array Initializations
In the function example_split() the following line:

    int x[10] = { 0, 1, 2, 2, 4, 5, 6, 6, 7, 9 };


would be easier to modify if it was written as:

    int x[] = { 0, 1, 2, 2, 4, 5, 6, 6, 7, 9 };


There is no need to include the size of the array for x because the compiler does it for you.

The size of the array can be calculated:

    int arr_size = (sizeof(x) / sizeof(x[0]));


The variable end_idx can then be calculated as well.

    int end_idx = (sizeof(x) / sizeof(x[0])) - 1;


For Loop Control Variables
In the function example_split() there is no need to create the variable i at the top, it can be created inside the for loop itself:

    for (int i = 0; i &lt; arr_size; i++) {
        printf("%d,", x[i]);
    }


It's generally better to create the variables as they are needed. This is a change from the original version of the C Programming Language that was quite helpful.