161°

二分法查找(初学者)

适用情况:在一批有序数据中查找某数。

基本思想:

1 确定区间[a,b],验证f(a)·f(b)<0,给定精确度ξ.

2 求区间(a,b)的中点c.

3 计算f(c).

(1) 若f(c)=0,则c就是函数的零点;

(2) 若f(a)·f(c)<0,则令b=c;

(3) 若f(c)·f(b)<0,则令a=c.

(4) 判断是否达到精确度ξ:即若|a-b|<ξ,则得到零点近似值a(或b),否则重复2-4.

例:假设数组a中的数据是按由小到大的顺序排列的:-12,0,6,16,23,56,80,100,110,115,从键盘上输入一个数,判定该数是否在该数组中,若在,输出所在序号。

(假设输入的数为80)第一步:设low、mid和high三个变量,分别指向数列中的起始元素,其初始值为low=0,high=9,mid=4,判断mid指示的数是否为所求。mid指示的数是23,不是要找的80,仍继续查找。

第二步:确定新的查找区间,因为80大于23,所以查找的范围可以缩小为23后面的数,新的查找区间为[56,80,100,110,115],low,mid,high分别指向新区间的开始,中间和最后一个数。实际上high不变,将low(low=mid+1)指向56,mid(mid=(low+high)/2)指向100,还不是要找的80,仍继续查找。

第三步:上一步中,所找数80比mid指示的100小,可知新的查找区间为[56,80],low不变,mid与high的值作相应修改。mid指示的数为56,还要继续查找。

第四步:根据上一步的结果,80大于mid指示的数56,可确定新的查找区间为[80],此时,low与high都指向80,mid亦指向80,即找到了80,到此为止,查找过程完成。

注:若在查找过程中,出现low>high的情况,则说明,序列中没有该数,亦结束过程。

参考程序:

#include <stdafx.h>
#include<stdio.h>

void main()
{
    int a[10]={-12,0,6,16,23,56,80,100,110,115},low,mid,high,found,n;
    low=0;
    high=9;
    mid=4;
    found=0;
    printf("Input a number to be searched:");
    scanf("%d",&n);
    for(;low<=high;mid=(low+high)/2)
    {
        if(n==a[mid])
        {
            found=1;
            break;
        }
        if(n>a[mid])
        {
            low=mid+1;
        }
        else
        {
            high=mid-1;
        }
    }
    if(found==1)
    {
        printf("The index of %d is %d",n,mid);
    }
    else
    {
        printf("There is not %d",n);
    }
    

}

 

 

 

 

原文链接:https://www.cnblogs.com/lvfengkun/p/10322084.html

全部评论: 0

    我有话说: