筑基

• 1 泛型函数bsearch()的编写过程
• • 1.1 先实现对整型数组的查找
  • 1.2 尝试使用泛型
  • 1.3 增加对负数和指针数组的支持
• 2 测试
• • 2.1 对指针数组的二分查找

int8_t BinarySearch(int key, int *arr, uint8_t arrLen)
{
    uint8_t low = 0;
    uint8_t high = arrLen-1;
    uint8_t middle;
    // In ascending order
    while(low <= high) {
        middle = (low + high)>>1;
        if(arr[middle] == key) {
            return middle;
        } else if (arr[middle] > key) {
            high = middle - 1;
        } else {
            low = middle + 1;
        }
    }
    return -1;
}

void *bsearch(void *key, void *arr, 
			uint8_t arrLen, uint8_t elemSize)
{
    uint8_t low = 0;
    uint8_t high = arrLen - 1;
    uint8_t middle;
    void *elemAddr;
	// In ascending order
    while(low <= high) {
        middle = (low + high) >> 1;
        elemAddr = (char *)arr + middle * elemSize;
        if(0 == memcmp(key, elemAddr, elemSize)) {
            return elemAddr;
        } else if(memcmp(key, elemAddr, elemSize) > 0 ) {
            low = middle + 1;
        } else {
            high = middle - 1;
        }
    }
    
    return NULL;
}

void *bsearch(void *key, void *arr, 
			uint8_t arrLen, uint8_t elemSize, 
			int cmpFn(void*, void*))
{
    uint8_t low = 0;
    uint8_t high = arrLen - 1;
    uint8_t middle;
    void *elemAddr;
    int result;
	// In ascending order
    while(low <= high) {
        middle = (low + high) >> 1;
        elemAddr = (char *)arr + middle * elemSize;

        result = cmpFn(key, elemAddr);
        if(0 == result) {
            return elemAddr;
        } else if(result > 0 ) {
            low = middle + 1;
        } else {
            high = middle - 1;
        }
    }
    
    return NULL;
}

int bIntCmp(void *elem1, void *elem2)
{
    int *ip1 = (int *)elem1;
    int *ip2 = (int *)elem2;
    return *ip1 - *ip2;
}

int bStrCmp(void *elem1, void *elem2)
{
    char *cp1 = *(char **)elem1;
    char *cp2 = *(char **)elem2;
    return strcmp(cp1, cp2);
}

int arr[] = {-100, -25, -1, 0, 1, 5, 6, 10, 11, 12, 15};
char *str[] = { // ordered list, ascending order
    "ab",
    "abc",
    "abcd",
    "abcde"
};

int main (int argc, char *argv[])
{
    char *strKey = "abc";
    void *get;

    printf("there are %d elems in arrayrn", sizeof(str)/sizeof(char *));
    get = bsearch( &strKey, &str, 
    			sizeof(str)/sizeof(char *), sizeof(char *), 
    			bStrCmp);
    if(NULL != get) {
        printf( "taget %s was founded in position %drn", strKey,  (char **)get - str);
    } else {
        printf("Not foundedrn");
    }

    return 0;
}