折半查找算法的实现 -电脑资料

电脑资料 时间:2019-01-01 我要投稿
【www.unjs.com - 电脑资料】

    算法设计思想如下:

    (1)设置初始区间,low=1;high=length,

折半查找算法的实现

    (2)当low>high时,返回查找失败信息。

    (3)取中点,low<=high,mid=(low+high)/2。

    a.若kx

    b.若kx>a[mid],查找改在右半区进行,low=mid+1;转向步骤(2)。

    c.若ax=a[mid],查找成功,返回数据位置。

    代码实现:

   

#include <stdio.h>int b_search(int x, int a[], int n)  //折半查找函数{    int low = 0;    int high = n ;    if (low > high)    {        return -1;    }    else    {        while (low <= high)        {            int mid = (low + high) / 2;            if (a[mid] < x)            {                low = mid + 1;            }            else if (a[mid] > x)            {                high = mid - 1;            }            else            {                return mid;            }        }    }         return -1;}int main(){    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };    int key = 0;    int sz = sizeof(arr) / sizeof(arr[0]);    scanf("%d", &key);        int ret = b_search(key, arr, sz);    if (ret == -1)    {        printf("不存在这个数!\n");    }    else    {        printf("%d\n", ret);    }    return 0;}

最新文章