How do I perform binary search on a text file to search a keyword in python?
Question: The text file contains two columns- index number(5 spaces) and characters(30
spaces). It is arranged in lexicographic order. I want to perform binary
search to search for the keyword.


Answer: Here's an interesting way to do it with Python's built-in bisect module.

    
    
    import bisect
    import os
    
    
    class Query(object):
    
        def __init__(self, query, index=5):
            self.query = query
            self.index = index
    
        def __lt__(self, comparable):
            return self.query < comparable[self.index:]
    
    
    class FileSearcher(object):
    
        def __init__(self, file_pointer, record_size=35):
            self.file_pointer = file_pointer
            self.file_pointer.seek(0, os.SEEK_END)
            self.record_size = record_size + len(os.linesep)
            self.num_bytes = self.file_pointer.tell()
            self.file_size = (self.num_bytes // self.record_size)
    
        def __len__(self):
            return self.file_size
    
        def __getitem__(self, item):
            self.file_pointer.seek(item * self.record_size)
            return self.file_pointer.read(self.record_size)
    
    
    if __name__ == '__main__':
        with open('data.dat') as file_to_search:
            query = raw_input('Query: ')
            wrapped_query = Query(query)
    
            searchable_file = FileSearcher(file_to_search)
            print "Located @ line: ", bisect.bisect(searchable_file, wrapped_query)
    

