Binary search array representing "continuous" ranges. {0, 10, 20} = 0-9, 10-19, 20-infinite

gistfile1.c

static NSUInteger binary_search_range_index(NSUInteger *positions,
                                            NSUInteger len,
                                            NSUInteger n) {
    NSInteger current = len / 2;
    NSUInteger delta = len / 2;
    
    while (!(n >= positions[current] &&
             (current == len-1 || n < positions[current+1]))) {
        delta = delta / 2;
        if (delta == 0) {
            delta = 1;
        }
        if (positions[current] > n) {
            current -= delta;
        } else {
            current += delta;
        }
    }
    
    return current;
}

static NSUInteger naive_search_range_index(NSUInteger *positions,
                                           NSUInteger len,
                                           NSUInteger n) {
    for (NSUInteger i = 0; i < len-1; i++) {
        if (n < positions[i+1]) {
            return i;
        }
    }
    
    return len-1;
}

static NSUInteger test_search_range_index(NSUInteger *positions,
                                          NSUInteger len,
                                          NSUInteger n) {
    NSUInteger binary = binary_search_range_index(positions, len, n);
    NSUInteger naive = naive_search_range_index(positions, len, n);
    
    if (binary != naive) {
        NSLog(@"DIFF");
    }
    
    return binary;
}

static void test_case(NSUInteger *positions,
                      NSUInteger len,
                      NSUInteger n,
                      NSUInteger expected) {
    
    NSUInteger binary = binary_search_range_index(positions, len, n);
    NSUInteger naive = naive_search_range_index(positions, len, n);
    
    NSLog(@"%@ binary=%ld naive=%ld expected=%ld",
          binary != expected || naive != expected ? @"FAIL :" : @"MATCH:",
          binary, naive, expected);
}

void test_cases(void) {
    NSUInteger test1[] = {0, 10};
    NSUInteger test2[] = {0, 10, 20, 30};
    NSUInteger test3[] = {0, 1, 2, 3};

    test_case(test1, 2, 0, 0);
    test_case(test1, 2, 1, 0);
    test_case(test1, 2, 10, 1);
    test_case(test1, 2, 11, 1);
    
    test_case(test2, 4, 0, 0);
    test_case(test2, 4, 5, 0);
    test_case(test2, 4, 10, 1);
    test_case(test2, 4, 15, 1);
    test_case(test2, 4, 19, 1);
    test_case(test2, 4, 20, 2);
    test_case(test2, 4, 35, 3);

    test_case(test3, 4, 0, 0);
    test_case(test3, 4, 1, 1);
    test_case(test3, 4, 2, 2);
    test_case(test3, 4, 3, 3);
    test_case(test3, 4, 4, 3);
}

static void dump(NSUInteger *positions,
                 NSUInteger len) {
    for (NSUInteger i = 0; i < len; i++) {
        NSLog(@"%ld: %ld", i, positions[i]);
    }
}