DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Roger has posted 34 posts at DZone. View Full User Profile

Two Binary Search Functions In C

11.12.2008
| 7150 views |
  • submit to reddit
        // Two versions of binary search -- one recursive, one iterative -- for an array of strings.
// Both assume that your array index fits within an integer.

/* 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;
}