C语言-数据结构 折半查找

        在折半查找中，刚开始学可能会在下标处产生困惑，例如奇数个长度的数组怎么处理，偶数个长度的数组怎么处理，不需要修改代码吗？并且下标我从1开始算和0开始算影响代码吗？其实都可以用一样的代码，产生困惑的原因我觉得是例子不够，虽然你感觉理解了思想，但是对于这些细节的地方还是容易头大，可以自行列举出奇数长度有序数组、偶数长度有序数组、折半算法代码修改为下标从0开始数的、1开始数的（数组0位置不存储元素）你会惊讶的发现原来都可以找到，这些例子在你的手动计算下都跑通的话，我想你就算掌握折半查找的算法了！

下面代码我分别列举出奇数个数数组、偶数个数数组以及两种折半函数从0开始计算和从1开始计算

#include <stdio.h>
// 二分查找函数
//Binary_Search1代码中下标从1开始查找，n为数组的最大索引=实际数组长度-1
int Binary_Search1(int* a, int n, int key) {
    int low, high, mid; // 定义低、高索引和中间索引
    low = 1;            // 设置低索引为1（假设数组从下标1开始）
    high = n;          // 设置高索引为n（即数组的最后一个元素的索引）
    // 进入循环，直到low超过high
    while (low <= high) {
        mid = (low + high) / 2; // 计算中间索引
        if (key < a[mid]) {     // 如果目标值小于中间元素
            high = mid - 1;     // 更新高索引为中间索引的前一个元素
        }
        else if (key > a[mid]) { // 如果目标值大于中间元素
            low = mid + 1;      // 更新低索引为中间索引的下一个元素
        }
        else {
            return mid;         // 返回找到的位置下标
        }
    }
    return -1; // 如果未找到目标值，返回0
}
//代码中下标从0开始查找，n为数组的最大索引=实际数组长度-1
int Binary_Search2(int* a, int n, int key) {
    int low, high, mid; // 定义低、高索引和中间索引
    low = 0;            // 设置低索引为1（假设数组从下标1开始）
    high = n;          // 设置高索引为n（即数组的最后一个元素的索引）
    // 进入循环，直到low超过high
    while (low <= high) {
        mid = (low + high) / 2; // 计算中间索引
        if (key < a[mid]) {     // 如果目标值小于中间元素
            high = mid - 1;     // 更新高索引为中间索引的前一个元素
        }
        else if (key > a[mid]) { // 如果目标值大于中间元素
            low = mid + 1;      // 更新低索引为中间索引的下一个元素
        }
        else {
            return mid;         // 返回找到的位置下标
        }
    }
    return -1; // 如果未找到目标值，返回0
}
int main() {
    // 初始化一个有奇数个元素的数组
    int jishu[] = { 0, 1, 16, 24, 35, 47, 59, 62, 73, 88, 99,100 };
    // 初始化一个有偶数个元素的数组
    int oshu[] = { 0, 1, 16, 24, 35, 47, 59, 62, 73, 88, 99 };
    // 调用二分查找函数并打印结果
    // 注意：传入的数组长度应为有效元素个数
    printf("下标从1开始查找\n");
    printf("奇数数组查找100结果为：%d\n", Binary_Search1(jishu, 11, 100));
    printf("偶数数组查找99结果为：%d\n", Binary_Search1(oshu, 10, 99));
    printf("奇数数组查找0结果为：%d\n", Binary_Search1(jishu, 11, 0));
    printf("偶数数组查找0结果为：%d\n", Binary_Search1(oshu, 10, 0));
    printf("\n下标从0开始查找\n");
    printf("奇数数组查找100结果为：%d\n", Binary_Search2(jishu, 11, 100));
    printf("偶数数组查找99结果为：%d\n", Binary_Search2(oshu, 10, 99));
    printf("奇数数组查找0结果为：%d\n", Binary_Search2(jishu, 11, 0));
    printf("偶数数组查找0结果为：%d\n", Binary_Search2(oshu, 10, 0));
    return 0; 
}

运行结果

原文地址：https://blog.csdn.net/BamBoo_Bean/article/details/142865645

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！