Применение линейного и бинарного поиска к массивам

Мне нужно создать программу, которая принимает пользовательский ввод (число), а затем программа должна иметь этот номер, применять поиск к массиву и выводить соответствующий заголовок, сопоставляя индекс и число, введенное пользователем. Однако во время выполнения ничего не происходит. Я установил прерыватели в своем коде и заметил проблему с циклом for (алгоритм поиска). Пожалуйста, помогите мне и дайте мне знать, что не так с моим алгоритмом поиска. То, что я пытаюсь сделать, это использовать число, которое пользователь вводит, чтобы соответствовать индексу, а затем выводить название книги, которое хранится в индексе.

       private void btnFindActionPerformed(java.awt.event.ActionEvent evt) {                                        
    // TODO add your handling code here:  

    // declares an array 
   String[] listOfBooks = new String [101];

   // assigns index in array to book title 
   listOfBooks[1] = "The Adventures of Tom Sawyer"; 
   listOfBooks[2] = "Huckleberry Finn"; 
   listOfBooks[4] = "The Sword in the Stone";
   listOfBooks[6] = "Stuart Little";
   listOfBooks[10] = "Treasure Island";
   listOfBooks[12] = "Test";
   listOfBooks[14] = "Alice's Adventures in Wonderland";
   listOfBooks[20] = "Twenty Thousand Leagues Under the Sea";
   listOfBooks[24] = "Peter Pan";
   listOfBooks[26] = "Charlotte's Web";
   listOfBooks[31] = "A Little Princess";
   listOfBooks[32] = "Little Women";
   listOfBooks[33] = "Black Beauty";
   listOfBooks[35] = "The Merry Adventures of Robin Hood";
   listOfBooks[40] = "Robinson Crusoe";
   listOfBooks[46] = "Anne of Green Gables";
   listOfBooks[50] = "Little House in the Big Woods";
   listOfBooks[52] = "Swiss Family Robinson";
   listOfBooks[54] = "The Lion, the Witch and the Wardrobe";
   listOfBooks[54] = "Heidi";
   listOfBooks[66] = "A Winkle in Time";
   listOfBooks[100] = "Mary Poppins";

    // gets user input 
    String numberInput = txtNumberInput.getText();
    int number = Integer.parseInt(numberInput);

    // Linear search to match index number  and user input number
        for(int i = 0; i < listOfBooks.length - 1; i++) {
        if (listOfBooks.get(i) == number) {
        txtLinearOutput.setText(listOfBooks[i]);
        break; 
        }


    }

*Существует проблема с listOfBooks.get в операторе if. Также мне нужно применить бинарный поиск, который будет искать тот же массив, просто используя бинарный метод. Нужна помощь, чтобы применить этот тип бинарного поиска.

Как мне сделать оператор, который проверяет, равно ли число int индексу?

Обратите внимание, что следующий код является лишь примером того, что я должен применить. Все переменные предназначены для примера:

public static Boolean binarySearch(String [ ] A, int left, int right, String V){
     int middle;

     if (left > right) {
         return false;
     }

     middle = (left + right)/2;
     int compare = V.compareTo(A[middle]);
     if (compare == 0) {
         return true;
     }
     if (compare < 0) {
         return binarySearch(A, left, middle-1, V);
     } else {
         return binarySearch(A, middle + 1, right, V);
     }
 }

person Jack Armstrong    schedule 19.08.2015    source источник
comment
вы сопоставляете название книги с введенным номером, что не имеет смысла   -  person SSH    schedule 19.08.2015
comment
Вы хотите изучить BinarySearch? Если нет, вы могли бы использовать List или Map, это становится очень простым и выполняет поиск почти за время O (1).   -  person Uma Kanth    schedule 19.08.2015
comment
Как я могу сопоставить входной номер с номером индекса?   -  person Jack Armstrong    schedule 19.08.2015
comment
Я хочу изучить и использовать BinarySearch.   -  person Jack Armstrong    schedule 19.08.2015
comment
Ах! для использования BinarySearch strings должно быть sorted.   -  person Uma Kanth    schedule 19.08.2015
comment
если вы поместите какой-либо неиндексный номер, вы получите исключение OutOFBound Exception, вот как вы можете проверить его, иначе ваш номер в порядке, надеясь, что вы напишете какой-то код для этой логики,   -  person SSH    schedule 19.08.2015


Ответы (5)


вы можете избежать for loop и проверить состояние, просто указав число, подобное этому: txtLinearOutput.setText(listOfBooks[number-1]);

удалить свой код

// Linear search to match index number  and user input number
for(int i = 0; i < listOfBooks.length - 1; i++) {
    if (listOfBooks.get(i) == number) {
     txtLinearOutput.setText(listOfBooks[i]);
     break; 
}

с

try{
     int number = Integer.parseInt(numberInput);
     if(number>0 && number<101){
       txtLinearOutput.setText(listOfBooks[number-1]);
     }else{
        // out of range
     }
 }catch(Exception e){
   // handle exception here
 }
person Rustam    schedule 19.08.2015
comment
Спасибо! Я понял. Теперь мне нужна помощь с бинарником! - person Jack Armstrong; 19.08.2015
comment
для бинарного поиска ваш массив должен быть отсортирован - person Rustam; 19.08.2015

Вы сравниваете if (listOfBooks.get(i) == number), это неправильно, вы должны сравнить: if (i == number), потому что вам нужно сравнить положение элемента.

person Ivan Khotynskyi    schedule 19.08.2015

Это не ответ бинарного поиска. Просто реализация HashMap. Посмотри на это.

HashMap<String, Integer> books = new HashMap();
books.put("abc", 1);
books.put("xyz", 2);
books.put("pqr", 3);
books.put("lmo", 4);

System.out.println(books.getValue("abc");

Использование встроенного BinarySearch.

String []arr = new String[15];
arr[0] = "abc";
arr[5] = "prq";
arr[7] = "lmo";
arr[10] = "xyz";
System.out.println(Arrays.binarySearch(arr, "lmo"));

Как сравнить Strings с помощью бинарного поиска.

String[] array = new String[4];
        array[0] = "abc";
        array[1] = "lmo";
        array[2] = "pqr";
        array[3] = "xyz";
        int first, last, middle;
        first = 0;
        last = array.length - 1;
        middle = (first + last) / 2;
        String key = "abc";
        while (first <= last) {
            if (compare(array[middle], key))
                first = middle + 1;
            else if (array[middle].equals(key)) {
                System.out.println(key + " found at location " + (middle) + ".");
                break;
            } else {
                last = middle - 1;
            }
            middle = (first + last) / 2;
        }
        if (first > last)
            System.out.println(key + " is not found.\n");

    }

    private static boolean compare(String string, String key) {
        // TODO Auto-generated method stub
        for (int i = 0; i < Math.min(string.length(), key.length()); ++i)
            if (string.charAt(i) < key.charAt(i))
                return true;
        return false;

    }
person Uma Kanth    schedule 19.08.2015
comment
LOL Я хотел бы, чтобы это было так просто, но я должен применить его с кодом, который я там разместил. - person Jack Armstrong; 19.08.2015

Ваш код линейного поиска выглядит примерно так

try{
txtLinearOutput.setText(listOfBooks[yourNumber]);
}
catch(IndexOutOfBoundsException ie){
// prompt that number is not an index
}
catch(Exception e){
// if any other exception is caught
}
person SSH    schedule 19.08.2015

Что вы здесь делаете:

if (listOfBooks.get(i) == number) {

заключается в том, что вы сопоставляете содержимое массива с входным числом, что не имеет значения.

Вы можете напрямую использовать входной номер для получения значения, хранящегося в индексе.

Например:
txtLinearOutput.setText(listOfBooks[number-1]);

Кроме того, int number = Integer.parseInt(numberInput); следует поместить в блок try-catch, чтобы проверить синтаксический анализ входного числа. И вы можете проверить, находится ли входное число в пределах диапазона массива, чтобы избежать таких исключений, как:

try{

    int number = Integer.parseInt(numberInput);

    // Linear search to match index number  and user input number
    if (number > 0 && number <=100) {
        txtLinearOutput.setText(listOfBooks[number-1]);
    } else {
    // Display error message
    }
} catch(Exception e) {
    // Handle exception and display error message
}

А для использования бинарного поиска массив строк необходимо отсортировать. Вы можете использовать метод Arrays.sort() для сортировки. Что касается использования бинарного поиска, вы можете использовать Метод двоичного поиска массивов Java

person Maverick    schedule 19.08.2015