二分搜索
一．实验目的：
1.理解算法设计的基本步骤及各步的主要内容、基本要求；
2.加深对分治设计方法基本思想的理解，并利用其解决现实生活中的问题；
3.通过本次实验初步掌握将算法转化为计算机上机程序的方法。
二．实验内容：
1.编写实现算法：给定n个元素，在这n个元素中找到值为key的元素。
2.将输入的数据存储到指定的文本文件中，而输出数据存放到另一个文本文件中，包括结果和具体的运行时间。
3.对实验结果进行分析。
三．实验操作：
1.二分搜索的思想：
首先，假设表中的元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
重复上述过程，知道找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
由于二分搜索是基于有序序列的一种搜索算法，故将输入的一组数据首先进行排序，考虑到输入数据可能有多个，采用快速排或者是合并排序，其中与冒泡做了对比。
冒泡排序算法：
void sort(int List[],int length){
int change;
for(int i=0;i<length;i++)
for(int j=i+1;j<length;j++){
if(List[i]>List[j]){
change=List[i];
List[i]=List[j];
List[j]=change;
}
}
}
快速排序算法：
void Qsort(int List[],int low,int high){
if(low>=high) return;
int first=low;
int last=high;
int key=List[first];
while(first<last){
while(first<last&&List[last]>=key) --last;
List[first]=List[last];
while(first<last&&List[first]<=key) ++first;
List[last]=List[first];
}
List[first]=key;
Qsort(List,low,first-1);
Qsort(List,last+1,high);}
二分查找算法：
int binarySearch(int List[],int low,int high,int key){
int mid=(low+high)/2;
if(high<low) return -1;
while(low<=high){
if(List[mid]==key) return mid+1;
else{
if(List[mid]>key) return binarySearch(List,low,mid-1,key);
else return binarySearch(List,mid+1,high,key);
}
}
}
2.实验数据的输入：
本实验采用将数据输入与输出存储到文件中的方式，需要采用C++文件流操作，对于数据的输入，由于cin对数据的读取会忽略空格和换行操作，使用cin 流输入来控制数据的输入。
对于输出操作，首先要从文件中读取数据，为了区别各数据，用逗号隔离，经过处理后将数据存入到另一文件之中。
由于输入需要大量的数据，可采用从“随机数.txt”中读取数据。
存入文件算法：
int input(){
ofstream outFile;
outFile.open("E://程序设计/practice 1/算法设计与分析文本文件夹
D/number.txt",ios::trunc);
if(!outFile.is_open()) cout<<"File can't open!"<<endl;
cout<<"输入数据Y:"<<endl;
char number;
int length=0;
cin>>number;
while(number!='E'){
length++;
outFile<<number;
cin>>number;
}
outFile.close();
return length;
}
文件数据提取算法：
int* output(int length){
ifstream inFile;
ofstream outFile;
inFile.open("E://程序设计/practice 1/算法设计与分析/文本文件夹D/number.txt");
outFile.open("E://程序设计/practice 1/算法设计与分析/文本文件夹D/result2.txt",ios::trunc);
char* Array=new char[length];
int* List=new int[length/2];
int i=0,j=0;
outFile<<"数组中的元素为：";
while(!inFile.eof()){
inFile>>Array[i];
if(Array[i]!=','&&i<length-1){
List[j]=Array[i]-'0';
outFile<<List[j]<<" ";
j++;
}
i++;
}
sort(List,length/2);
inFile.close();
outFile.close();
return List;
}
3.程序运行时间测量:
为了得到二分搜索的时间，主要是排序的时间，调用time标准库，通过对起止时间记录，得到运行时间。
double start,end,Time;
start=clock();
调用程序；
end=clock();
Time=end-start;
四．实验数据分析：
当测试的数据较少时，如输入个数为20个时，两种排序时间都为0，即两种排序所消耗的时间差不多。
在数据小于2000个时，它们的耗费时间是代价相等的。
但当数据规模十分庞大时，快速排序的时间代价远远低于冒泡排序，例如当输入的数据为3000个时，快速排序的时间消耗是冒泡排序的1/3,由此可见一斑，并且当输入的数据完全逆序时，快速排序将和冒泡排序一样复杂。
最后将排序的时间与查找的时间相加，即为二分搜索的总时间，为
n(logn)+time.
五．实验感受：
在本次实验中，测试程序的运行时间时，需要用到大量的数据，仅仅输入100以内的数据对时间的测试不起作用，故用随机数生成并读取，解决了测试时间不明显的问题。
而对于输入的数据，其顺序也有一定影响性。