MENU

折半查找函数的循环结构

• November 3, 2020 • 递归

重新编写折半查找函数int BSearch(int arr[],int x,int low,int height),要求把函数设计成循环结构


题目分析:

说一下折半查找函数,要在一个数组里面找一个数,前提是这个数组是有序的(这儿我们认为是递增的哈),我们首先把数组分成两半,我们把中间的那个数字和要查找的数据x比较,如果x大于中间的数,那么我们就在右边找,有把右边当成一个新的递增数组,再把这个新数组分成两半,以此类推,这就叫折半查找,直到找到数据x为止,如果数组不存在x,就返回-1

然而,题目要我们设计成循环结构,照上面说的思路,差不多就是循环结构了吧,聪明机智的你看出来了吗


图例演示:


代码实现:

#include<stdio.h>
#include<stdlib.h>
/*二分折半查找法,成功返回数据在数组的下标值,否则返回-1*/
int BSearch(int arr[], int x, int low, int height)
{
    while (low<height)//循环结构
    {
        int mid = (low + height) / 2;//找中间下标
        if (x < arr[mid])    //如果小于中间的数,在左边寻找
            height = mid;
        else if (x > arr[mid])//如果大于中间的数,在右边寻找
            low = mid + 1;
        else                //如果等于中间的数,直接返回下标值
            return mid;
    }
    return -1;                //没有查询到,返回-1
}
int main()
{
    printf("数组有多少个数:");
    int n,arr[100];
    scanf_s("%d", &n);
    for (int i = 0; i < n; i++)
        scanf_s("%d", &arr[i]);
    printf("请输入要查找的数:");
    int data;
    scanf_s("%d", &data);
    int result = BSearch(arr, data, 0, n - 1);
    if (result!=-1)
        printf("\n数据 %d 在数组中的下标是 %d\n",data, result);
    else
        printf("数组中没有数据 %d\n", data);
    system("pause");
    return 0;
}

运行结果:


正常查找



正常查找



数据不再数组内



代码编译器:Visual Studio 2017
ok

Archives QR Code Tip
QR Code for this page
Tipping QR Code