4.13一维数组的应用 例4.1算法分析 从最后一位学生到第一位学生依次与输入成绩进行比较, 以下标0处的数组元素作为监视哨 考虑到本例的 score数组下标0处并未存情任何数据元素, 我们可以以它作为监视哨,从而提高程序的效率 输入待查找成绩x 设置监视哨 SCorE[0]=x for(i=n-1, score[i]l =x i--) >0 是 查找成功,输出i输出查找不成功
4.1.3 一维数组的应用 例4.1 算法分析 • 从最后一位学生到第一位学生依次与输入成绩进行比较， 以下标0处的数组元素作为监视哨 • 考虑到本例的score数组下标0处并未存储任何数据元素， 我们可以以它作为监视哨，从而提高程序的效率
4.13一维数组的应用 例4.1算法分析 从最后一位学生到第一位学生依次与输入成绩进行比较, 以下标0处的数组元素作为监视哨 score[O]=X /在下标处设置视哨 for(i= n; score[i]!=x: i-- //计数循环,从后到前循环比较当前元素,循“空语句 if(i>=1) cout<<"査找成功,待查找成绩是第“ <<i<”位学生的成绩"<endl; 0e{0 se cout<<"未查找到该成绩!"<end1;
4.1.3 一维数组的应用 例4.1 算法分析 • 从最后一位学生到第一位学生依次与输入成绩进行比较， 以下标0处的数组元素作为监视哨 score[0] = x; // 在下标处设置监视哨 for(i = n; score[i] != x; i--); // 计数循环，从后到前循环比较当前元素，循环体为空语句 if(i >= 1) { cout<<"查找成功，待查找成绩是第“ <<i<<" 位学生的成绩"<<endl; } else { cout<<"未查找到该成绩！"<<endl; }
4.13一维数组的应用 14. 2 oN C: windows system32\cmd 入1个 数 果在, 输生成绩 :80828486889092949698 请输入待查找的学生成绩9 i位学 生日查找成功,待查找成绩是第6位同学的成绩 算法分请按任意键继续 先找到中间元素,再根据中间元素与待查找元素的比较结果缩 小一半的待查找区间,从而提高查找的效率。 如果中间元素与待查找元素相等,则查找成功 如果中间元素较大,则待查找元素在前半区间,查找前半区间 如果中间元素较小,继续查找后半区间 使用两个整型变量分别表示区间的上界和下界。 如果区间的上界小于下界,说明区间为空,查找失败。 比较后,要查找前半区间,只需修改区间的上界;要查找后半 区间,只需修改区间的下界
4.1.3 一维数组的应用 例4.2 有10位学生的成绩存放在数组score中，从键盘输入1个 数，使用折半查找法查找这个成绩是否在数组中，如果在， 输出其下标，如果不在，输出0。数组的下标i表示第i位学 生的成绩，数组的下标0处不存储成绩。 算法分析： 先找到中间元素，再根据中间元素与待查找元素的比较结果缩 小一半的待查找区间，从而提高查找的效率。 如果中间元素与待查找元素相等，则查找成功 如果中间元素较大，则待查找元素在前半区间，查找前半区间 如果中间元素较小，继续查找后半区间。 使用两个整型变量分别表示区间的上界和下界。 如果区间的上界小于下界，说明区间为空，查找失败。 比较后，要查找前半区间，只需修改区间的上界；要查找后半 区间，只需修改区间的下界
4.13一维数组的应用 例4.2有10位学生的成绩存放在数组 score中,从键盘输入1个 数,使用折半查找法查找这个成绩是否在数组中,如果在, 输出其下标,如果不在,输出0。数组的下标表示第位学 生的成绩,数组的下标处不存储成绩 算法的NS图 输入待查找成绩x 初始化待查找区间上下界1ow=1,high=n while(low(=high) 计算待查找元素下标mid=(1ow+high)/2 score lld=-X 是 否 score lmld/y 查找成功是 否 退出循环查找前半区间查找后半区间 highEmid-1 low-mid+1 low<=high 是 否 查找成功,输出nid 输出查找不成功
4.1.3 一维数组的应用 例4.2 有10位学生的成绩存放在数组score中，从键盘输入1个 数，使用折半查找法查找这个成绩是否在数组中，如果在， 输出其下标，如果不在，输出0。数组的下标i表示第i位学 生的成绩，数组的下标0处不存储成绩。 算法的NS图
41.3一维数组的应用 例4.2折半查找核心程序段 输入待查找成绩x wh16(w<=high一找初始化待查找区间上下界10m,ha while(low(=high mid=(low high)/2 计算待查找元素下标n(1o+hc) if( score [mid]==x)//中 score lmid==x 是 break score [mid]>x else if (score [mid >x)// 查找成功是 否 high= mid-1 查找前半区间查找后半区间 else HTTLLTT I low-mid+1 low mid +1 low<=high 是 否 if(low<=high 查找成功,输出nd|输出查找不成功 //待查找区间不为空,查找成功 cout<"查找成功,待査找成绩是第“ mid<"位学生的成绩"<(end e⊥se /待查找区间为空,查找不成功 cout<"未査找到该成绩!"<<endl;
4.1.3 一维数组的应用 例4.2折半查找 核心程序段 while(low <= high) // 只有待查找区间不为空，就循环 { mid = (low + high) / 2; // 计算中间元素下标 if(score[mid] == x) // 中间元素与待查找元素相等，查找成功 break; // 退出循环 else if(score[mid] > x) // 中间元素较大，查找前半区间 high = mid - 1; // 修改待查找区间上界 else // 中间元素较小，查找后半区间 low = mid + 1; // 修改待查找区间下界 } if(low <= high) { // 待查找区间不为空，查找成功 cout<<"查找成功，待查找成绩是第“ <<mid<<" 位学生的成绩"<<endl; } else { // 待查找区间为空，查找不成功 cout<<"未查找到该成绩！"<<endl; }