Thread: recursive search function

Post a whole program so we don't have to write the rest to run it.
It also allows us to see how you are calling the function.

Again, it is generally considered idiotic to preface variables with type designators.

Anyway, iNum is just a pointer. It's sizeof is the size of a pointer, not of an array. Normally we would declare it as int *num, not int num[] to reflect this fact.

At any rate, you don't need the array's size since you have the start and end indices. The initial end index should be one-past-the-end (i.e., the size of the array).

Do not print anything in the function. The user of the function should decide whether and what to print. Instead, return -1 if the value is not found.

Your function is a little over-complicated. You certainly don't need to check the start and end positions.

It is best to return the result (not use a pointer).
That's what a return value is for.
Whenever it fits the situation it's pretty much always best to use it.

Code:

#include <stdio.h>
 
int search(const int *nums, int start, int end, int goal) {
    if (end - start < 1) return -1;
 
    int mid = (end - start) / 2 + start;
    if (nums[mid] == goal) return mid;
 
    // mid cannot be the goal, so don't include it
    return nums[mid] < goal
         ? search(nums, mid+1, end, goal)
         : search(nums, start, mid, goal);
}
 
int main() {
    int a[] = {2, 4, 5, 8, 10, 12, 15};
 
    for (int goal = 1; goal < 17; ++goal) printf("%2d ", goal);
    putchar('\n');
 
    for (int goal = 1; goal < 17; ++goal)
        printf("%2d ", search(a, 0, sizeof a / sizeof *a, goal));
    putchar('\n');
 
    return 0;
}

Output:
 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 
-1  0 -1  1  2 -1 -1  3 -1  4 -1  5 -1 -1  6 -1

Simpler, if you discount the unnecessary obfuscation of the comparison function.

its just dawned on me what you might of meant about prefacing variables

It's called Hungarian Notation and was originally invented for typeless languages, not a typed language like C. Microsoft used to use it but I don't think they recommend it anymore. Linus Torvalds calls it "brain-damaged".

@flp, I should've mentioned the possibility of using bsearch, but I assumed that he wanted to implement his own function.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
 
int cmpint(const void *a, const void *b) {
    const int *p = a, *q = b;
    return (*p > *q) - (*p < *q);
}
 
int main() {
    int a[] = {2, 4, 5, 8, 10, 12, 15};
 
    for (int key = 1; key < 17; ++key) printf("%2d ", key);
    putchar('\n');
 
    for (int key = 1; key < 17; ++key) {
        int *p = bsearch(&key, a, sizeof a / sizeof *a, sizeof *a, cmpint);
        printf("%2td ", p ? p - a : (ptrdiff_t)-1);
    }
    putchar('\n');
 
    return 0;
}