Posted By

rtperson on 02/04/12

Tagged

Versions (?)

Last Edited at 02/04/12 02:45am

Statistics

Viewed 783 times

Favorited by 0 user(s)

Related snippets

Two Binary Search Functions in C

/ Published in: C

Two versions of binary search -- one recursive, one iterative -- for an array of strings.
Both assume that your array index fits within an integer.

Highlighted TextExpand

/* iterative version */
int search2(char *dict, char *name, int compChars) {
    int low, high, mid, result;
    low = 0;
    high = SIZE_OF_DICTIONARY - 1;
    
    while (low <= high) {
        mid = (low + high) / 2;
        result = strncmp(dict[mid], name, compChars);
        if (result > 0) {
            high = mid - 1;
        } else if (result < 0) {
            low = mid + 1;
        } else {
            return EXIT_SUCCESS;
        }   
    }
    return NOT_FOUND;
}

/* recursive version -- takes more space and, for my money, is more confusing */
int search(char *dict, char *name, int low, int high, int compChars) {
    if (high < low) {
        return NOT_FOUND; 
    }
    int mid = (low + high) / 2;
    int result;
    result = strncmp(dict[mid], name, compChars);
    if (result > 0) {
        return search(name, low, mid-1, compChars);
    } else if (result < 0) {
        return search(name, mid+1, high, compChars);
    } else {
        return EXIT_SUCCESS; 
    }
    return ERROR_SEARCH;
}

Report this snippet Tweet