arrayscstringbsearch

Problem with bsearch() implementation with array of strings


As part of a coding task, I am trying to implement a version of bsearch() and I have experienced an issue with an array of strings.

this is the function I have created:

int binSearch(void *Arr, int Size, int ElemSize,
              void *Item, int (*compare)(void *, void *)) {
    BYTE *pArr = Arr;
    int found = NOT_FOUND;
    int left, right, mid, cmp;
    left = 0, right = (Size - 1);
    while (!found && left <= right) {
        mid = (left + right) / 2;
        cmp = compare(pArr + (mid * ElemSize), Item);
        if (cmp == 0)
            found = FOUND;
        else if (cmp < 0)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return found;
}

this function seems to work fine with int *Arr but not with char **Arr. the function returns NOT_FOUND even thou the string is indeed in the array.

this is the calling function and comparison function I have created:

#define SIZE 100 // max Len for str is 99 chars

int stringBinSearch(char **strings, int size, char *str) {
    return binSearch(strings, size, SIZE, str, compereByAscii);
}

int compereByAscii(char *str1, char *str2) {
    return strcmp(str1, str2);
}

from what it seems, its a problem with cmp = compare(pArr + (mid * ElemSize), Item);, but I can't figure it out.


Solution

  • The comparison function gets a pointer to the array element, not the array element it self, so you must change the code to:

    int compareByAscii(void *p1, void *p2) {
        char **strp1 = p1;
        char **strp2 = p2;
        return strcmp(*strp1, *strp2);
    }
    
    int stringBinSearch(char **strings, int size, char *str) {
        return binSearch(strings, size, sizeof(char *), &str, compareByAscii);
    }