方法来获得文件的中间为二进制搜索 [英] Method to get to the middle of the file for Binary Search
问题描述
我做的,我得给一个程序,读取数据文件和数据吐出成字节,其中前4个字节数组的告诉你,有多少人的名字有一个数组(赋值该数据文件包含)。以下持有人的名称的字符串数组的其余部分。该数组指向一个常量无效* foo的;
例如,前4个字节表示有存储到阵列5名,以及在接下来的4个字节告诉你的人的名字的地址。此人的名称存储阵列中的
INT NUM =((INT *)富)[0];
const int的ppl1 =((INT *)富)[1];
字符串名称=((字符*)富)+ ppl1;
所以 NUM
会告诉你那里有数组中的5名和 ppl1
会告诉你的阵列的位置在这里你可以找到名字和名称收集位于数组的插槽中的人的姓名。
pretty了,我取了一个名字在数组中搜索,我想用二进制搜索DOIT。我不知道的方式来查找文件的中间虽然,你们可以给我一些指点?
欢呼声=]
编辑:所以我创建了这一点,但它赛格故障,并只适用于一种情况下(第一项搜索时)。不知道为什么......
诠释第一= 0;
INT NUM =((INT *)富)[0];
INT最后= NUM;
而(第一< =上){
INT中间=第一+最后一/ 2;
偏移为int =((INT *)富)[中];
字符串名称=((字符*)富)+偏移;
如果(人<名){
最后=中间1;
}否则如果(人>名){
第一=中间+ 1;
}其他{
打破;
}
seekg
,和c 所以tellg
的功能++文件流将允许您浏览尽管此文件。
I am doing an assignment where I've got given a program which reads in a data file and spits out the data into an array of bytes, where the first 4 bytes of the array tell you how many people's names it has (the data file contains). Following the rest of the array which holds strings of the names of the people. This array is pointed to by a const void * foo;
For example, the first 4 bytes say there are 5 names stored into the array, and the next 4 bytes tell you the address of the person's name. The person's name is stored in the array
int num = ((int*)foo)[0];
const int ppl1 = ((int*)foo)[1];
string name = ((char*)foo)+ppl1;
so num
would tell you theres 5 names in the array and ppl1
would tell you the position of the array where you can find the first name and name collects the name of the person located at that slot of the array.
Pretty much, I am given a name to search for in the array, and I wanted to use binary search to doit. I don't know of a way to find the middle of the file though, can you guys give me some pointers?
cheers =]
EDIT: so I created this, but it seg faults and only works for one case (when searching for the first entry). No idea why...
int first = 0;
int num = ((int*)foo)[0];
int last = num;
while (first <= last) {
int middle = first+last/2;
int offset = ((int*)foo)[middle];
string name = ((char*)foo)+offset;
if (person < name) {
last = middle-1;
} else if (person > name) {
first = middle+1;
} else {
break;
}
The functions seekg
and tellg
of C++ file streams will allow you to navigate though the file.
这篇关于方法来获得文件的中间为二进制搜索的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!