Binary Search on a text file

Reply

Join Date: Jan 2005
Posts: 20
Reputation: scoobie is an unknown quantity at this point 
Solved Threads: 0
scoobie scoobie is offline Offline
Newbie Poster

Binary Search on a text file

 
0
  #1
Aug 23rd, 2006
Hi,

Can someone please help me. I have a really large text file that contains a list of hash values, it has about ten million entries. I wanted to do a binary search on this to check if a particular hash value is present in the file and to return true if it is and false if not. i have tried to write a binary search and have a small text file with nine entries. the problem i am having is that i don't know how to get it to jump to the middle of the file to begin the search from there without loading it into memory.

any help would be greatly appreciated,

thanks,

Kedklok.

Here's the code i tried:

  1.  
  2. import java.io.*;
  3. import java.util.*;
  4. class TokenizerExample3
  5. {
  6. public static String a[];
  7. public static int i=0;
  8.  
  9. public static int binarySearch(String[] a2, String searchItem)
  10. {
  11. int first=0;
  12. int last = array.length - 1;
  13. int middle;
  14.  
  15. boolean found = false;
  16.  
  17. //Loop until found or end of list.
  18. while(first <= last &&!found)
  19. {
  20. middle = (first + last) /2;
  21. if(array[middle]==(searchItem)) found = true;
  22.  
  23. else
  24. {
  25. if(array[middle]==(searchItem))
  26. last = middle -1;
  27. else first = middle + 1;
  28. }
  29. }// end while
  30.  
  31. if(found) return middle;
  32. else return(-1);
  33. }//end binary search
  34.  
  35. /* Main method */
  36. public static void main(String[] args) throws IOException
  37. {
  38. FileReader file = new FileReader("C:\\test.txt");
  39. BufferedReader fileInput = new BufferedReader(file);
  40. long numLines = 0;
  41.  
  42. String line;
  43. do
  44. {
  45. line = fileInput.readLine();
  46. if (line != null)
  47. {
  48. a[i] = line;
  49. numLines++;
  50. }
  51. i++;
  52. }
  53. while (line != null);
  54. String searchItem = "hello";
  55. //hello is at the 4th entry in the file
  56. binarySearch(a, searchItem);
  57. }//end main
  58. }end class
Reply With Quote Quick reply to this message  
Join Date: Jan 2005
Posts: 20
Reputation: scoobie is an unknown quantity at this point 
Solved Threads: 0
scoobie scoobie is offline Offline
Newbie Poster

Re: Binary Search on a text file

 
0
  #2
Aug 25th, 2006
Hi,

i got it to jump to the middle of the file. does anyone know how i would extract the string located at this point and compare it to my test string.

thanks,
scoobie
Reply With Quote Quick reply to this message  
Join Date: Mar 2004
Posts: 763
Reputation: Phaelax is on a distinguished road 
Solved Threads: 38
Phaelax Phaelax is offline Offline
Master Poster

Re: Binary Search on a text file

 
0
  #3
Aug 25th, 2006
Shouldn't this:
if(array[middle]==(searchItem))

be this:
if (array[middle].equals(searchItem))


If the length of the hash code is the same for all entries, then you should be able to determine the amount of bytes you need to skip.
  1. //8 characters plus 1 line-terminated character (\r, \n)
  2. int lineSizeInBytes = 9;
  3. //line in the file you want starting from 0
  4. int line = 5;
  5. RandomAccessFile raf = new RandomAccessFile("myFile.dat","r");
  6. raf.skipBytes(line*lineSizeInBytes);
  7. String hash = raf.readLine();
Reply With Quote Quick reply to this message  
Reply

This thread is more than three months old.
Perhaps start a new thread instead?
Message:


Thread Tools Search this Thread



About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC