YTU——问题 : 这样查找效率高

题目描述

在 n 个整数构成的有序序列中，找到关键字 key 在序列中出现的位置。当 key在序列中不出现时，输出 No。
为了提高查找效率，利用待查找序列有序的特征，程序使用“二分查找”的算法。二分查找的做法是：首先，将表中间位置记录的关键字与查找关键字 key 比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
在提示部分已经给出部分代码，将程序补充完整，并提交规定的部分。

输入

先输入 n 个表示待查找的序列中的元素个数。
再输入 n 个整数作为待查找序列，这些整数按从小到大的顺序排列。
最后输入要查找的数 key。

输出

输出 key 在序列出现的位置，若不出现，输出 No。

输入输出样例

样例输入 #1

10
2 4 5 6 8 22 37 65 75 88
5

样例输出 #1

3

提示

#include 
#define SIZE 100int find(int *, int, int);int main()
{int d[SIZE], i;int n, key, index;scanf("%d", &n);for (i= 0; i < n; i++)scanf("%d", &d[i]);scanf("%d", &key);index=find(d,n,key);if (index >= 0)printf("%d\n", index+1);elseprintf("No\n");return 0;
}/*******只提交下面的部分********/int find(int *d, int n, int k)
{int low= 0, high= SIZE-1, mid, index= -1;while (_____1______){mid= _____2_____;if (d[mid] == k){index= mid;_____3_____;}else if (_____4_____)high= mid-1;elselow= mid+1;}return index;
}

参考解答：

int find(int* d, int n, int k)
{int low = 0, high = n - 1, mid, index = -1;while (low <= high){mid = (low + high)/2;if (d[mid] == k){index = mid;break;}else if (d[mid]>k)high = mid - 1;elselow = mid + 1;}return index;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！