Binary Search Help : Reading File into Array, finding a specific line

Question

In the file, each entry will contain two lines; the first line is the number, and the second line is the title. The entries in the file will be in numerical ascending order.

Create a program that reads the a file into an array. The user will then request a title based on the number. Your program will perform a binary search to find the title.

Currently, I read everything from the file into an arrayList, and from there I convert it into an array.

My first major issue is that my binary search method does not appear to be working; I attempt to search for a number, and it simply returns false. Secondly, even if this manages to work, I am unsure of how to record which line in the text file the result was found in. I assume this is necessary, as I must output the line after. This is an example of what the text file looks like.

2

The messianic drama

4

Evening prayer

7

Prayer of the virtuous under persecution

etc. This is my current code

package Psalms;

import java.io.*;

import javax.swing.*;

import java.util.ArrayList;

import java.util.List;

public class Psalms {



public static void main(String[] args) throws IOException {
    // Creates array list. Reads lines into it
    List<String> psalms = new ArrayList<String>();
    BufferedReader readFile = new BufferedReader(new FileReader("Psalms.txt"));
    String line;
    while ((line = readFile.readLine()) != null) {
        psalms.add(line);
    }
   readFile.close();

    String[] psalmArray = new String[psalms.size()];
    psalmArray = psalms.toArray(psalmArray);

    //Asks user what to search for.
    String psalmSearch = (JOptionPane.showInputDialog("What number Psalm would you like to search for?"));
    System.out.println("Binary Search: " + psalmSearch + " " + binarySearch(
            psalmArray, 0, psalmArray.length - 1, psalmSearch));

}

public static boolean binarySearch(String myArray[], int left,
        int right, String searchForPsalm) {
    int middle;

    if (left > right) {
        return false;
    }
    middle = (left + right) / 2;
    if (myArray[middle].equals(searchForPsalm)) {
        return true;
    }
    if (searchForPsalm.compareTo(myArray[middle]) < 0) {
        return binarySearch(myArray, left, middle - 1,
                searchForPsalm);
    } else {
        return binarySearch(myArray, middle + 1, right,
                searchForPsalm);
    }
}

}

score 0 · Answer 1 · edited May 08 '14 at 04:35

Right now, what you are doing is adding one String per line in the file to a List. Thus, this List will look like this:

<"2", "The messianic drama", "4", "Evening prayer", "7">

The problem is that when you are attempting to perform a binary search on this, you are comparing some Strings with titles, and some with numbers.

Here is my recommended approach, assuming that the file you get is already sorted:

While you are reading lines of the file, alternate between adding them to two different lists, where one contains the title, and the other the number as an integer. When you add the number from the file, make sure to convert it to an integer using Integer.parseInt(String). The idea is to create two lists like this:

Title List = <"The messianic drama", "evening prayer", "Prayer of the virtuous under 
persecution">
Tile Number List: <2,4,7>

Do you see how the 2 is at the same index in the list as The messianic drama in the other?

Then, when you are performing your binary search looking for a title number, if you find the number that you are looking for, then just return the string in the title list at the same position.

If your titles are not numbered in order in the file, you may want to consider making a Tuple of String and Integer. That is a little more complicated, as you will have to make a class and implement a Comparator so you can sort them properly.

score 0 · Answer 2 · edited May 23 '17 at 12:11

Assuming your file is correctly validated (i.e. every psalm number is followed by a text line), then for the existing binarySearch method, there are 2 corrections needed:

    .
    .
    middle = (left + right) / 2;
    middle += middle & 1;  // to the nearest even number
    .
    .
    .
    } else {
        return binarySearch(myArray, middle + 2, right,
                searchForPsalm);
    }
}

1) As all psalm numbers are in the even array position, you need to ensure the middle is set to the nearest even offset.

2) For the 'right side' partition, you should skip over the text line by setting it to 'middle + 2'.

This will ensure that you are comparing the psalm numbers as intended.

Now rather than returning a boolean, you could return the string to display the associated text if found, so here is the revised method:

public static String  binarySearch(String myArray[], int left,
        int right, String searchForPsalm) {
    int middle;

    if (left > right) {
        return "";
    }
    middle = (left + right) / 2;
    middle += middle & 1;
    if (myArray[middle].equals(searchForPsalm)) {
        return myArray[middle + 1];
    }
    if (searchForPsalm.compareTo(myArray[middle]) < 0) {
        return binarySearch(myArray, left, middle - 1,
                searchForPsalm);
    } else {
        return binarySearch(myArray, middle + 2, right,
                searchForPsalm);
    }
}

It will return a empty string if no entry found.

In addition, if you need the 'middle' value also to be returned, you could revise it to return an object, say Result, which has both the 'middle' and the string value - see examples here:

How to return multiple values in java?

Binary Search Help : Reading File into Array, finding a specific line

2 Answers2