- #include <iostream>
- #include <fstream>
- #include <cstdio>
- #include <string>
- using namespace std;
- ifstream file("words.txt");
- int times = 0; //用于计算查找次数
- //used to binary search in the file
- long BinarySearch(long b, long e, string target) {
- long begin = b;
- long end = e; //end一直位于某一行的行首,即最后一行的行尾
- long middle = 0;
- string temp;
- while(begin < end) {
- times++;
- middle = (begin+end)/2;
- file.seekg(middle,file.beg);
- //判断是否刚好截在行尾
- char ch = file.get();
- if(ch == '\\n') { //若刚好截在行尾,则往前进一格(换行符占两个偏移量),方便后续操作
- middle -= 1;
- }
- file.seekg(middle,file.beg);
- getline(file,temp);
- if(middle+temp.size()+2 == end) { //若为最后一行,则将middle移至行首
- long i = 1;
- ch = '\\0';
- while (ch != '\\n' && middle-i >= begin) {
- file.seekg(middle-i, file.beg);
- ch = file.get();
- i++;
- }
- if(ch == '\\n')
- middle = middle - i + 2;
- else
- middle = begin;
- }
- else { //若非最后一行,则将middle移至下一行行首
- middle += temp.size() + 2;
- }
- file.seekg(middle,file.beg);
- getline(file,temp);
- if(temp == target) {
- return middle;
- }
- else {
- if(temp < target) {
- if(middle+temp.size()+2==end) return -1; //比最后一行要大,故不存在
- begin = middle;
- }
- else if(temp > target) {
- if(middle==begin) return -1; //比第一行要小,故不存在
- end = middle;
- }
- }
- }
- return -1;
- }
- int main() {
- string str, target;
- cin>>target;
- getline(file,str);
- if(str == target) { //第一行即为查找内容的情况
- cout<<"Found: "<<target<<endl;
- }
- else if(str > target) {
- cout<<"Too little!"<<endl;
- return 0;
- }
- else {
- //获取最后一行的内容
- char ch = '\\0';
- long i = 2; //文件最后一行至少有一个字符
- while(ch != '\\n') {
- file.seekg(-i, file.end);
- ch = file.get();
- i++;
- }
- getline(file,str);
- if(str == target) { //最后一行即为查找内容的情况
- cout<<"Found: "<<target<<endl;
- }
- else if(str < target) {
- cout<<"Too large!"<<endl;
- return 0;
- }
- else { //查找内容在文件中间的情况
- file.seekg(0,file.end);
- long len = file.tellg();
- file.seekg(0,file.beg);
- long res = BinarySearch(0,len-str.size(),target);
- cout<<"times: "<<times<<endl;
- if(res == -1) {
- cout<<"Not Found!"<<endl;
- }
- else {
- file.seekg(res,file.beg);
- getline(file,str);
- cout<<"Found: "<<str<<endl;
- }
- }
- }
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/1508201410184.html
来源: http://www.codesnippet.cn/detail/1508201410184.html