二分查找问题(共5页).docx

精选优质文档-倾情为你奉上一、 二分查找问题1) 实验问题：a) 设a0:n-1是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。b) 设有n个不同的整数排好序后存放于t0:n-1中，若存在一个下标i，0in，使得ti=i，设计一个有效的算法找到这个下标。2) 基本思想：将n个元素分成个数大致相同的两半，取an/2与x作比较。如果x=an/2，则找到x，算法终止。如果xan/2，则只要在数组a的右半部分继续搜索x。3) 算法流程图：4) 测试数据及结果运行图：a)b)5) 源代码：a) #includeint findnum(int *a,int n,int x,int &lower,int& higher)