算法之二分查找的算法

在这个算法中, 我们将在一个包含 n 个元素的数组 M 中查找一个元素 x。 算法假设 M 已经按升序排列了。

二分搜索算法
第一步: 将 low 置为0, high 置为 n-1;
第二步: 如果 low>high 那么 x 不在 M 中, 算法结束。
第三步: 将 mid 设为 (low+high)/2;
第四步: 如果 M[mid]第五步: 如果 M[mid]>x 那么将 high 设为 mid-1 并且转向第二步;
第六步: M[mid] 与 x 相等算法结束。

我们可以使用这个算法写一个函数, 在这个字典中查找一个词, 如果找到, 返回项目号否则返回 -1。

程序

int lookup(struct entry dictionary[],char search[],int num)
{
    int low=0, high=num-1;
    int mid, result;
    while (low <= high)
    {
        mid = (low + high)/2;
        result=strcmp(dictionary[mid].word, search);
        if (result == -1) low = mid+1;
        else if (result == 1) high=mid-1;
        else return(mid);/* found it */
    }
    return(-1); /* not found */
}

main()
{
    static struct entry dictionary[100] ={{"aardvark","a burrowing African mammal"},
        {"abyss", "a bottomless pit" },{"acumen", "mentally sharp; keen" },
        {"addle","to become confused" },{"aerie", "a high nest"}, ...... ...... };
    char word[10];
    int entrys = 10,num;
    printf("Enter word:\n");
    scanf("%s",word);
    num = lookup(dictionary,word,entrys);
    if (num != -1)
        printf("%s\n",dictionary[num].definition);
    else printf("Sorry,that word is not in my dictionary.");
}