C++ 迭代器二分搜索方法示例
参考:C++ Primer中文版(第五版)
注:在项目代码目录中需要包含输入文件、输出文件。
头文件:
#include <iostream>
using std::cin; using std::cout; using std::endl; using std::cerr;
#include <fstream>
using std::ifstream; using std::ofstream;
#include <vector>
using std::vector;
#include <iterator>
using std::iterator;
实现代码:
{
ifstream inf;//文件输入流,向程序输入一批integer
vector<int> iVec{};//保存从文件输入流inf中输入的integers
int iSearch{ 0 };//保存要查询的integer
cout << "Enter an integer to be researched: ";
cin >> iSearch;//向程序输入要查询的integer
inf.open(argv[1], ifstream::in);//打开输入文件
if (!inf)//打开输入文件失败,程序退出
{
cerr << "Can't open input file " << argv[1] << "." << endl;
return EXIT_FAILURE;
}
int iTemp{ 0 };//保存文件输入流中单个integer
while (inf>>iTemp)//从文件输入流中逐个向程序输入integer,并保存在iTemp
{
iVec.push_back(iTemp);//按照输入顺序,逐个保存文件输入流inf中的integers
}
inf.close();//关闭文件输入流与输入文件的绑定
//迭代器二分搜索
vector<int>::const_iterator cbeg = iVec.cbegin();//在顺序容器iVec中进行二分搜索的初始左闭合范围的开始元素迭代器
vector<int>::const_iterator cend = iVec.cend();//在顺序容器iVec中进行二分搜索的初始左闭合范围的的结尾元素迭代器
vector<int>::const_iterator cmid = iVec.cbegin() + (iVec.cend() - iVec.cbegin()) / 2;//在顺序容器iVec中进行二分搜索的初始左闭合范围的的中间元素迭代器
//当还有元素尚未检查并且没有找到要查询的iSearch时执行循环
while ((cmid!=cend)&&(*cmid!=iSearch))
{
if (*cmid > iSearch)//要查询的元素在前半部分
cend = cmid;//忽略掉后半部分,中间元素不是要查询元素,可做为左闭合范围的右值
else//要查询的元素在后半部分
cbeg = cmid + 1;//忽略掉前半部分,中间元素不是要查询元素,也可以忽略
cmid = cbeg + (cend - cbeg) / 2;//新左闭合范围的中间元素
}
ofstream outf;//文件输出流,从程序向输出文件写入查询结果
outf.open(argv[2], ofstream::out | ofstream::app);//打开输出文件,尾部分追加模式
if (!outf)//打开输出文件失败,程序退出
{
cerr << "Can't open output file " << argv[2] << "." << endl;
return EXIT_FAILURE;
}
if (cmid == cend)
outf << "Can't find " << iSearch << "." << endl;//文件输出流,从程序向输出文件写入查询结果
else
outf << iSearch << " is find in the " << cmid - iVec.cbegin() + 1 << " position of " << argv[1] << "." << endl;//文件输出流,从程序向输出文件写入查询结果
outf.close();//关闭文件输出流与输出文件的绑定
}
转载于:https://blog.51cto.com/9737702/1963997