[one_demo_11]二分查找法

àì夳堔傛蜴生んèń 2022-05-31 08:37 91阅读 0赞

#define _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    #include<stdlib.h>
    #include<time.h>
    
    
    /*
    函数作用，冒泡排序
    参数，source，数组地址；len，数组长度；orderby，排序方式，1小到大，否则反之
    返回值，参数正确返回1，否则返回0
    */
    int sort(int source[], int len, int orderby)
    {
    if (source == NULL || len == 0)
    {
    return 0;
    }
    for (int i = 0; i < len - 1; i++)
    {
    for (int j = 0; j < len - 1 - i; j++)
    {
    if (orderby == 1)
    {
    if (source[j] > source[j + 1])
    {
    int temp = source[j];
    source[j] = source[j + 1];
    source[j + 1] = temp;
    }
    }
    else
    {
    if (source[j] < source[j + 1])
    {
    int temp = source[j];
    source[j] = source[j + 1];
    source[j + 1] = temp;
    }
    }
    }
    }
    }
    
    
    /*
    函数功能，从排序的整数数组中，二分查找某个整数
    参数，source，要查找的对象数组；len，数组的长度；dest，要找的数
    返回值，void
    */
    void searcher(int source[], int len, int dest)
    {
    //判断参数的合法性
    if (source == NULL || len == 0)
    {
    printf("参数不合法\n");
    return;
    }
    //循环二分，结束条件为下限大于上限
    int down = 0;//下限的下标
    int up = len - 1;//上限的下标
    int mid = 0;
    while (down <= up)
    {
    //获取上限和下限的中值
    mid = (down + up) / 2;
    if (source[mid] == dest)
    {
    //数组中值等于目标，找到，返回数组中值
    printf("要找的数的下标为%d\n", mid);
    return;
    }
    else if (source[mid] > dest)
    {
    //如果数组中值大于目标，则改上限为中值
    up = mid - 1;
    }
    else
    {
    //如果数组中值小于目标，则改下限为中值
    down = mid + 1;
    }
    }
    //如果循环结束仍没有找到，则说明不在这个数组中，返回0
    printf("不存在要找的数\n");
    }
    
    
    
    
    //递归实现二分查找，实际上，在算法比较简单的情况下，递归的劣势，即效率低，更明显
    //考虑到递归的效率问题，在递归函数内部不作参数的合法性判断
    /*
    函数功能，递归二分查找一个整数数组中是否存在某个整数
    参数，source，int[]型，要查找的数组；down，int型，下限下标；up，int型，上限下标；dest，int型，要找的数
    返回值，用以标识是否找到要找的数，返回1找到，否则，没有。
    */
    int searcherd(int source[], int down, int up, int dest)
    {
    if (down > up)
    {
    printf("没有找到要找的数\n");
    return;
    }
    int mid = (down + up) / 2;
    if (source[mid] == dest)
    {
    printf("要找的数在数组的下标为%d\n", mid);
    return 1;
    }
    else if (source[mid] > dest)
    {
    up = mid - 1;
    searcherd(source, down, up, dest);
    }
    else
    {
    down = mid + 1;
    searcherd(source, down, up, dest);
    }
    }
    
    
    void main()
    {
    //使用随机数创建数组
    time_t ts;
    srand((unsigned int)time(&ts));//随机数种子
    int source[100] = { 0 };
    for (int i = 0; i < 100; i++)
    {
    source[i] = rand() % 100;
    printf("%-5d", source[i]);
    if (i % 10 == 9)
    {
    printf("\n");
    }
    }
    int sortres = sort(source, 100, 1);
    if (sortres == 0)
    {
    printf("参数错误，无法排序\n");
    }
    else
    {
    printf("排序后\n");
    for (int i = 0; i < 100; i++)
    {
    printf("%-5d", source[i]);
    if (i % 10 == 9)
    {
    printf("\n");
    }
    }
    }
    //调用二分查找函数，查找输入的数
    printf("请输入要查找的数\n");
    int dest = 0;
    scanf("%d", &dest);
    searcher(source, 100, dest);
    printf("使用二分递归查找\n");
    int dest2 = 0;
    scanf("%d", &dest2);
    int res = searcherd(source, 0, 100, dest2);
    system("pause");
    }