Advanced Search

Return to Snippet

Revision: 55374
at February 4, 2012 02:45 by rtperson
Initial Code 
/* 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;
}
Initial URL 

                                

                                                            

                                    

                                        

                                        Initial Description
                                        

                                    

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

                                

                                                            

                                    

                                        

                                        Initial Title
                                        

                                    

                                    
Two Binary Search Functions in C

                                

                                                            

                                    

                                        

                                        Initial Tags
                                        

                                    

                                    
search, c

                                

                                                            

                                    

                                        

                                        Initial Language
                                        

                                    

                                    
C