Применение линейных и двоичных поисков к массивам

Question

Мне нужно создать программу, которая вводит пользовательский ввод (число), а затем программа должна иметь этот номер и применять поиск к массиву и выводить соответствующий заголовок, сопоставляя индекс и номер введенного пользователем. Однако во время выполнения ничего не происходит. Я установил прерывания в свой код и заметил проблему с циклом 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); 
    } 
} 

Answer 1

вы можете избежать 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 
} 

Answer 2

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

Answer 3

Это не ответ двоичного поиска. Просто реализация 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; 

    } 

Answer 4

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

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

является то, что вы соответствие содержимого массива с входным номером, который не имеет отношения.

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

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

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

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 Arrays Binary Search method

Answer 5

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

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