multiple results in binary search when knowing first character of an word in java

Question

Below you can see my code. It reads from sort.txt in which there are words from dictionary. It saves them to arraylist3. I need to do binary search from that list. For example:

If user inputs

A

The program does binary search of list3 in which there are words with length 3 and returns all possible solutions.

At the moment program only return position if full word is inputed: So you need to input Aba and it return position but i need it to do as example below.

Example what program should do:

list3: [Aba, Aca, Ada, Baa, bbb, ddd, jjj]

User enters:

A

Program returns: Aba at position 0, Aca at position 1, Ada at postion 2.

That what I have so far. Please help kinda stuck here. Ignore the regular expresion comparison.

public class proba{


private final static int NOT_FOUND = -1;

public static void main(String[] args) {
String izbira;
int dolzina=0;
Scanner in = new Scanner(System.in);
String user_input;
Scanner input = new Scanner(System.in);

List<String> list3 = new ArrayList<String>();


try {

    File file = new File("sort.txt");
    FileReader fileReader = new FileReader(file);
    BufferedReader bufferedReader = new BufferedReader(fileReader);
    String vrstica;

    while ((vrstica = bufferedReader.readLine()) != null) {

        if (vrstica.length() == 3) {
            list3.add(vrstica);

        }
    }
    System.out.println(list3);
    do{
        do {
            System.out.println("Enter lenght of word:");
            if (in.hasNextInt()) {
                dolzina = in.nextInt();
            } else if (in.hasNextLine()) {
                System.out.printf("Wrong entry!%n ",
                        in.nextLine());
            } 
        } while (dolzina <= 0);

    Collections.sort(list3);

    System.out.println("Enter the first character of a word you are searching:");
    user_input = input.nextLine();
    //user_input = user_input.replace("*", ".");

    System.out.println("Sorted list: [length: " + list3.size() + "]");
    System.out.println(list3);


    if (dolzina == 3) {

            int index = binarySearch(list3, user_input);
            System.out.println("Found" + user_input +" at " + index);

    }

    dolzina=-1;
    System.out.println("Ponovni vnos (da/ne):");
    Scanner inn= new Scanner (System.in);
    izbira = inn.next();

}while (izbira.equalsIgnoreCase("da"));
    bufferedReader.close();
} catch (IOException e) {
    e.printStackTrace();

}
}


public static int binarySearch(List<String> integerList, String searchValue) {

int low = 0;
int high = integerList.size() - 1;
int mid = (low + high) / 2;

while (low <= high && !integerList.get(mid).equalsIgnoreCase(searchValue)) {

if (integerList.get(mid).compareTo(searchValue) < 0) {
    low = mid + 1;
} else {
    high = mid - 1;
}

mid = (low + high) / 2;

if (low > high) {
    mid = NOT_FOUND;
}

}
return mid;

 }

 }

Answer 1

you need to change this line:

while (low <= high && !integerList.get(mid).equalsIgnoreCase(searchValue)) {

to be

while (low <= high && ! integerList.get( mid ).contains( searchValue ) ) {

you're doing exact match where you want to be seeing if the string contains your character.

or, if you just want words that start with your substring

while (low <= high && ! integerList.get( mid ).toUpperCase().startsWith( searchValue.toUpperCase() ) ) {

cheers