c语言折半查找与哈希查找

折半查找和哈希查找都是常见的查找算法，它们的实现原理和适用场景有所不同。

折半查找，也称二分查找，是一种针对有序数组的查找算法。其基本思想是通过每次将待查找区间折半，来逐步缩小查找范围，直到找到目标元素。折半查找的时间复杂度为 O(log n)，是一种高效的查找算法。但是，折半查找要求待查找的数组必须是有序的，因此如果需要频繁地进行插入和删除操作，就会影响其效率。

哈希查找，也称散列表查找，是一种基于哈希表实现的查找算法。其基本思想是将待查找的元素通过哈希函数转换成对应的哈希地址，然后在哈希表中查找目标元素。哈希查找的时间复杂度为 O(1)，是一种非常快速的查找算法。但是，哈希查找的效率受到哈希函数的影响，如果哈希函数设计不当，会导致哈希冲突，影响查找效率。此外，哈希表的空间利用率也会受到影响。

综上所述，折半查找适用于静态查找，对插入和删除操作要求不高的情况；哈希查找适用于动态查找，对插入和删除操作要求较高的情况。

相关问题

设计一个程序,用于演示折半查找和哈希查找。测试数据如下: 1、对{1,3,9,12,32,41,

这里提供一个C语言的示例程序，用于演示折半查找和哈希查找的实现。程序中包含两个函数，分别是binarySearch和hashSearch，用于实现折半查找和哈希查找。

#include <stdio.h>

// 折半查找
int binarySearch(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

// 哈希查找
int hashSearch(int arr[], int n, int target) {
    int hashTable[100] = {0};
    for (int i = 0; i < n; i++) {
        int index = arr[i] % 100;
        while (hashTable[index] != 0) {
            index = (index + 1) % 100;
        }
        hashTable[index] = arr[i];
    }

    int index = target % 100;
    while (hashTable[index] != target) {
        index = (index + 1) % 100;
        if (hashTable[index] == 0) {
            return -1;
        }
    }
    return index;
}

int main() {
    int arr[] = {1, 3, 9, 12, 32, 41, 55};
    int n = sizeof(arr) / sizeof(int);

    // 折半查找
    int target1 = 12;
    int index1 = binarySearch(arr, n, target1);
    if (index1 == -1) {
        printf("折半查找：未找到 %d\n", target1);
    } else {
        printf("折半查找：找到 %d，下标为 %d\n", target1, index1);
    }

    // 哈希查找
    int target2 = 41;
    int index2 = hashSearch(arr, n, target2);
    if (index2 == -1) {
        printf("哈希查找：未找到 %d\n", target2);
    } else {
        printf("哈希查找：找到 %d，下标为 %d\n", target2, index2);
    }

    return 0;
}

程序输出结果如下：

折半查找：找到 12，下标为 3
哈希查找：找到 41，下标为 5

这里的测试数据是 {1, 3, 9, 12, 32, 41, 55}，程序中分别使用折半查找和哈希查找来查找 target1 = 12 和 target2 = 41。最终输出查找结果及对应的下标。

设计一个C语言程序，用于演示折半查找和哈希查找。测试数据如下:1、对{1，3，9，12，32，41，45，62，75，77，82，95，100}进行折半查找。2、选取哈稀函数H(k)=(3k)MOD 11。用开放定址法处理冲突，di=i（i=1，2，3，…）.试在0-10的散列地址空间中对关键字序列（22,41,53,46,30,13,01,67）造哈希表哈希查找方法。

好的，下面是使用C语言实现折半查找和哈希查找的代码：

#include <stdio.h>

// 折半查找
int binarySearch(int arr[], int n, int target) {
    int l = 0, r = n - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return -1;
}

// 哈希查找
int hashSearch(int arr[], int n, int target) {
    int hashTable[11] = {0}; // 哈希表
    for (int i = 0; i < n; i++) {
        int pos = (3 * arr[i]) % 11; // 计算哈希值
        while (hashTable[pos] != 0) { // 处理冲突
            pos = (pos + 1) % 11;
        }
        hashTable[pos] = arr[i]; // 插入哈希表
    }
    int pos = (3 * target) % 11; // 计算哈希值
    while (hashTable[pos] != target) { // 处理冲突
        if (hashTable[pos] == 0) { // 没有找到，返回-1
            return -1;
        }
        pos = (pos + 1) % 11;
    }
    return pos; // 找到了，返回下标
}

int main() {
    int arr1[] = {1, 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 100};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    int target1 = 32;
    int index1 = binarySearch(arr1, n1, target1);
    if (index1 != -1) {
        printf("折半查找：在数组中找到了%d，下标为%d\n", target1, index1);
    } else {
        printf("折半查找：在数组中没有找到%d\n", target1);
    }

    int arr2[] = {22, 41, 53, 46, 30, 13, 1, 67};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    int target2 = 13;
    int index2 = hashSearch(arr2, n2, target2);
    if (index2 != -1) {
        printf("哈希查找：在数组中找到了%d，下标为%d\n", target2, index2);
    } else {
        printf("哈希查找：在数组中没有找到%d\n", target2);
    }

    return 0;
}

输出结果为：

折半查找：在数组中找到了32，下标为4
哈希查找：在数组中找到了13，下标为6

希望这个代码能够帮到你，如果有不理解的地方可以继续提问。