递归型二分查找的C语言泛型实现

• 1 练习目的
• 2 代码
• 3 测试用例
• • 3.1 测试数据
  • 3.2 测试例程

1 练习目的

• 熟练掌握地址运算
  C语言中两个地址不能相加，但是能相减。二分算法，肯定需要定位到被查找数组的中间位置！

如何实现数组中间地址的定位？

不能使用：
( p S t a r t + p E n d ) / 2 → m i d (pStart + pEnd) / 2\rightarrow mid (pStart+pEnd)/2→mid
指针不能相加！！！但是可以相减啊！！！

( p S t a r t + ( p E n d − p S t a r t ) 2 × e l e m S i z e × e l e m S i z e ) → m i d (pStart + \frac{(pEnd - pStart)}{2 \times elemSize} \times elemSize) \rightarrow mid (pStart+2×elemSize(pEnd−pStart)​×elemSize)→mid

void *mid = (char *)arr + ((((char *)end - (char *)arr) / elemSize) >> 1) * elemSize;

2 代码

void *bsearch_recursion(void *key, void *arr, void *end, int elemSize, int cmpFn(void *, void *))
{// Space upward growth
   if(arr > end){
        return NULL;
    }else{
        void *mid = (char *)arr + ((((char *)end - (char *)arr) / elemSize) >> 1) * elemSize;
        if(cmpFn(key, mid) == 0){
            return mid;
        }else if(cmpFn(key, mid) < 0){
            end = mid - elemSize;
        }else{
            arr = mid + elemSize;
        }

        return bsearch_recursion(key, arr, end, elemSize, cmpFn);
    }
}

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

int CharCmp(void *elem1, void *elem2)
{
    char *cp1 = (char *)elem1;
    char *cp2 = (char *)elem2;

    return *cp1 - *cp2;
}

// Floating point numbers must be converted to integers for processing
int FloatCmp(void *elem1, void *elem2)
{// Accurating to four decimal places
    float *cp1 = (float *)elem1;
    float *cp2 = (float *)elem2;

    return (int)(*cp1 * 10000) - (int)(*cp2 * 10000);
}

int StrCmp(void *elem1, void *elem2)
{
    char *vp1 = *(char **)elem1;
    char *vp2 = *(char **)elem2;

    return strcmp(vp1, vp2);
}

3 测试用例

3.1 测试数据

int arr[] = {1, 6, 9, 21, 100, 155, 165, 243, 255};

char str[] = "abcdefg";

float f_arr[] = {0.1, 0.2, 0.3, 0.4, 1.1, 2.20, 2.21, 2.22, 2.3, 2.4};

char *str_arr[] = { // pointer array
    "a",
    "ab",
    "abc",
    "abcd",
    "abcde",
    "abcdef",
};

3.2 测试例程

int main(int argc, char *argv[])
{
    void *found = NULL;

    int target = 255;
    // found = lsearch(&target, arr, sizeof(arr)/sizeof(int), sizeof(int), IntCmp);
    // found = bsearch(&target, arr, sizeof(arr)/sizeof(int), sizeof(int), IntCmp);
    found = bsearch_recursion(&target, &arr, &arr[sizeof(arr)/sizeof(int) - 1], sizeof(int), IntCmp);
    if(found != NULL){
        printf("In address 0x%.8x, target(%d) is founded.\r\n", found, *(int *)found);
        printf("Index of \"%d\" is %d.\r\n", *(int *)found, (int *)found - (int *)arr);
    }else{
        printf("Not founded!\r\n");
    }

    char ch = 'c';
    // found = lsearch(&ch, str, sizeof(str)/sizeof(char), sizeof(char), CharCmp);
    found = bsearch_recursion(&ch, str, &str[sizeof(str)/sizeof(char) - 1], sizeof(char), CharCmp);
    if(found != NULL){
        printf("In address 0x%.8x, target('%c') is founded.\r\n", found, *(char *)found);
        printf("Index of \"%c\" is %d.\r\n", *(char *)found, (char *)found - (char *)str);
    }else{
        printf("Not founded!\r\n");
    }

    float f = 2.4;
    // found = lsearch(&f, f_arr, sizeof(f_arr)/sizeof(float), sizeof(float), FloatCmp);
    // found = bsearch(&f, f_arr, sizeof(f_arr)/sizeof(float), sizeof(float), FloatCmp);
    found = bsearch_recursion(&f, f_arr, &f_arr[sizeof(f_arr)/sizeof(float) - 1], sizeof(float), FloatCmp);
    if(found != NULL){
        printf("In address 0x%.8x, target('%f') is founded.\r\n", found, *(float *)found);
        printf("Index of \"%f\" is %d.\r\n", *(float *)found, (float *)found - (float *)f_arr);
    }else{
        printf("Not founded!\r\n");
    }

    char *str = "abc"; // Requiring a 2-level pointer
    // found = lsearch(&str, str_arr, sizeof(str_arr)/sizeof(char *), sizeof(char *), StrCmp);
    // found = bsearch(&str, str_arr, sizeof(str_arr)/sizeof(char *), sizeof(char *), StrCmp);
    found = bsearch_recursion(&str, str_arr, &str_arr[sizeof(str_arr)/sizeof(char *) - 1], sizeof(char *), StrCmp);
    if(found != NULL){
        printf("In address 0x%.8x, target('%s') is founded.\r\n", found, *(char **)found);
        printf("Index of \"%s\" is %d.\r\n", *(char **)found, (char **)found - (char **)str_arr);
    }else{
        printf("Not founded!\r\n");
    }

    return 0;
}