已知N元整型数组a存放N个学生的成绩，已按由大到小排序，试设

[问答题]

已知N元整型数组a存放N个学生的成绩，已按由大到小排序，试设计一个算法，用折半查找方法统计成绩大于或等于x分的学生人数。

牛客751798080号

#define N /*学生人数*/
int uprx(int a[N],int x )    /*函数返回大于等于X分的学生人数*/
 {
int low=1,mid,high=N;
do {
mid=(low+high)/2;
if(a[mid]>=x) _(1)_  else _(2)_;
}while(__(3)__);
if (a[low]<x) return low-1;
return low;
}

参考https://wenku.baidu.com/view/ae2a9be8e009581b6bd9eb75.html

（1）low=mid+1

(2) high=mid-1

(3) high>=low

这时需要找的是最后一个大于等于x的下标，若查找成功其下标为m，则有m个学生成绩大于或等于x，若查找不成功，若此时low所指向的值小于x，则有low-1个学生成绩大于或等于x（数组索引从1开始）

发表于 2020-11-10 11:18:10 回复(0)