Binary Search on a sorted file in Java

Binary search on a sorted array/list is quite trivial. But at times, you might get a file having sorted items and asked to find if a given item exists in it or not?

If the number of elements in the file is less, you can easily stream file in an array and then apply binary search. But what if the size of the file is huge or you don't have enough available memory to read the full content in an array. Can we apply binary search directly on file? YES!!!

Random Access File

Java I/O API provides a class named as RandomAccessFile. It has a different behavior than other InputStream or OutputStream classes. RandomAccesFile allows you to move forward and backward within the file using seek() method. It also provides length() method to give the maximum size of the file. And you can open a file either in read mode or read/write mode by passing "r" or "rw" in the constructor. 

Write sorted integers to a file:

 RandomAccessFile file = 
               new RandomAccessFile("sortedFile.txt", "rw");

for (int i = 0; i < 10; i++) {

file.writeInt(i * i);

}

file.close(); 

Java Implementation 

Below binary search implementation on a file.

 /**
  * Binary search
  * 
  * @param fileName
  *            input file name
  * @param num
  *            target input to be searched
  * @return true if search is successful
  */
 public boolean binarySearch(String fileName, int num) {
  Objects.requireNonNull(fileName, "valid filename is required !");

  // printFile(fileName);
  try {
   RandomAccessFile raf = new RandomAccessFile(fileName, "r");
   int first = raf.readInt();
   if (num == first)
    return true;

   int count = (int) (raf.length() >> 2);
   int midIndex, midValue, endIndex = count - 1, startIndex = 0;

   while (startIndex <= endIndex) {
    midIndex = (endIndex + startIndex) >> 1;

    // move file pointer to midIndex
    raf.seek(midIndex * 4);

    midValue = raf.readInt();
    if (midValue == num) {
     return true;
    } else {
     if (midValue > num) {
      endIndex = midIndex - 1;
     } else {
      startIndex = midIndex + 1;
     }
    }
   }
   raf.close();
  } catch (FileNotFoundException e) {
   e.printStackTrace();
  } catch (IOException e) {
   e.printStackTrace();
  }
  return false;
 }

--
keep coding !!!