折半查找算法实现(C++).doc

/此程序是折半查找的详细算法实现#includeusing namespace std;void CreateData(int data,int length);/为一个数组赋值/此函数是折半查找函数。其中data是所查寻的数组，length是数组的长度。x是所要查找的数，返回的值是数据x在数组中的位置int Bisearch(int data,int x,int begin,int last);/折半查找函数，使用过程中只需要给出数组名字，要查找的数值x，数组的起始位置begin及莫位置即可。void PrintData(int data,int length);/输出一个数组的所有元素。void main()/声明一个数组data10,并调用CreateData()函数为该数组赋值。int data10;CreateData(data,10);/调用PrintData()函数输出data的值。PrintData(data,10);loop:/定义一个整形变量用于接收用于要查找的数值,并提示用于输入该值int x;coutx;system(cls);PrintData(data,10);/调用函数Bisearch()函数查找用于输入的x在数组中的元素。int loaction = Bisearch(data,x,0,9);/首先判断是否查找成功if( loaction = -1)cout查找失败，没有你要查找的值endl;/当查找成功的情况下输出用户值所在的位置。elsecout你要查找的值x的位置在第：loaction+1个位置!endl;goto loop;/生成数据函数的定义。void CreateData(int data,int length)for(int i=0;ilength;i+)datai =i;/void CreateData(int data,int length)void PrintData(int data,int length)cout你所要输出的数组的元素有：;for (int i=0;ilength;i+)coutdatai ;coutlast)return -1;exit(0);int mid=(begin + last) /2;/如果x与数组中datamid的值相等，则查找成功，本函数执行完毕。if (x = datamid)return mid;exit(0);/当xdatamid的时候,则进行作面查找数据x。采用递归方法实现。if ( x datamid )Bisearch(data,x,begin ,mid-1);/如果xdatamid的情况下，即往数组的有半部分扫描数组。elseBisearch(data,x,mid+1 ,last);（2）# include void creat_ShuZu(int num,int length)/创建长度是length的数组numint i;for(i=0; ilength; +i) printf(第 %d 个元素：, i+1); scanf(%d, &numi); printf(数组创建完成！n);void jiangXu(int num,int length)/降序排列数组num中的元素int i,j;int temp;/临时变量for(i=0; ilength-1; +i)for(j=i; jlength-1; +j) if (numi numj+1)/numi与numj+1值互换 temp = numi;numi = numj+1;numj+1 = temp; printf(%d ,numi);printf(%dn,num9);void zheBan_Search(int need_find_num,int num,int length)/折半查找算法查询整型数字need_find_num是否在数组num中int low,mid,high;int flag = 0; low = 1;high = length;while (low = high)mid = (low + high)/2;if (need_find_num nummid-1)high = mid - 1;else flag = mid;printf(查询结果： 找到了,数%d在数组的第%d位n,need_find_num,flag);break; if (flag = 0)printf(查询结果： %d不是该数组中的元素n,need_find_num);int main(void)/主函数 int num10 ;int need_find_num;/需要在数组num中查询的整型数字printf(创建一个长度是10的数组: n); creat_ShuZu(num,10);printf(将数组中的元素降序排列: n); jiangXu(num,10);char isContinue ;printf(y或Y)开始查找，其他退出：);fflush(stdin);scanf (%c,&isContinue);while (isContinue = y | isContinue = Y)printf(请输入一个要查找的整型数据：);scanf(%d, &need_find_num);printf(折半算法查询%d是否为数组中的一个元素.n,need_find_num);zheBan