Binary Search on a text file
 

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:

import java.io.*; 

import java.util.*;

class TokenizerExample3 

{

   public static String a[];

   public static int i=0;

   

   public static int binarySearch(String[] a2, String searchItem) 

   {

        int first=0;

        int last = array.length - 1;

        int middle;

            

        boolean found = false;

            

        //Loop until found or end of list.

        while(first <= last &&!found) 

        {

          middle = (first + last) /2;

          if(array[middle]==(searchItem)) found = true;

          

          else 

          { 

             if(array[middle]==(searchItem))

             last = middle -1;

             else first = middle + 1;

           }

         }// end while

           

            if(found) return middle;

            else return(-1);

        }//end binary search

        

         /* Main method */

    public static void main(String[] args) throws IOException 

    {

        FileReader file = new FileReader("C:\\test.txt");

        BufferedReader fileInput = new BufferedReader(file);

        long numLines = 0;

                

        String line;

        do 

        {

           line = fileInput.readLine();

           if (line != null)

        {

        a[i] = line;

        numLines++;                                

        }

        i++;

        }

                while (line != null);

                String searchItem = "hello"; 

                  //hello is at the 4th entry in the file

                binarySearch(a, searchItem);

}//end main        

}end class

Re: Binary Search on a text file
 

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

Re: Binary Search on a text file
 

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.

//8 characters plus 1 line-terminated character (\r, \n)

int lineSizeInBytes = 9; 

//line in the file you want starting from 0

int line = 5; 

RandomAccessFile raf = new RandomAccessFile("myFile.dat","r");

raf.skipBytes(line*lineSizeInBytes);

String hash = raf.readLine();