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] ==> 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] > 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] < 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<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, &depth);
printf("\nFirst index into:\n\tx = (");
for (i=0; i<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;
}
