关于不读取 全部数据进内存的二分折半查找法的应用

编程语言用java
现在有一个字典数据文件，格式如下：
.........

就是一个单词＋0x00 ＋ int整形（4字节）＋ int整形（4字节）
举例：
a 0x00 0x00 0x00 0x00 0x0a 0x00 0x00 0x00 0x2d aba 0x00 0x00 0x00 0x00 0x01 0x00 0x00 0x00 0x35......
字典按字母顺序已经排序。
如果把这些词全部读入内存，然后用二分折半查找其实很简单，现在问题是由于在手持设备上读取，不能全部读入内存再查找。如果不用二分法非常慢。
但是如果用了二分法，实时定位困扰我很久，一直无法解决。因为加入文件长20000，第一次定位在10000的位置，这个位置如果出现在string里面，那么继续往下读到0x00，就可以判断单词结束，继续往下读两个int即可。但是如果出现在int数据间，那就无法用0x00来作为分隔符了，因为int本身的四个byte就可能含0x00。z 这样我没法知道哪个位置开始是string。
如果用c，有个函数可以直接读byte，自动读取当前位置后面的string，但是java就没办法了。
数据文件结构不能更改，请教大家有没有什么巧妙的办法可以不读入内存直接二分法查询？
谢谢！
[b]问题补充：[/b]
我自己也也用了索引法，我是这么建索引的:

这里的int就是字典文件里string的offset，我是按头字母和每隔100个string采用一个作为索引，就是这样，索引文件还是有500kb，500kb对小型设备还是比较多。
我觉得肯定有更好的索引创建方法，比如先按第一个字母作索引，再按头两个字母做索引，不过还没想到怎么创建这个索引文件比较高效和尺寸小.