将线性和二进制搜索应用于数组

Applying Linear and Binary Searches to Arrays

我必须创建一个接受用户输入(一个数字)的程序,然后程序应该有那个数字并对数组应用搜索并通过匹配索引和用户输入的数字输出相应的标题.然而在 运行 时间内,没有任何反应。我在我的代码中设置了断路器,并注意到 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; 
        }


    }

*if语句中的listOfBooks.get有问题。此外,我还需要应用二进制搜索,仅使用二进制方法搜索相同的数组。需要帮助来应用这种类型的二进制搜索。

我如何创建一个语句来检查 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);
     }
 }

你可以避免 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
 }

你在比较if (listOfBooks.get(i) == number)是错误的,你应该比较:if (i == number),因为你需要比较元素位置。

这不是二进制搜索答案。只是 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");

使用内置的二进制搜索。

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;

    }

你在这里做什么:

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

您的线性搜索代码看起来像这样

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