ArrayListのバイナリ検索アルゴリズム/ソートは文字列ですか？

Question

私が受けている授業の1つに、次のような質問があります。

6. ArrayListを検索するメソッドを作成する必要があります。 a。 ソート機能を含む検索方法には、バイナリ検索アルゴリズムを使用します。 Java.util.Arrays.binarySearch（）メソッドを使用しないでください。ただし、 はバイナリ検索アルゴリズムコードを記述します。 b。配列要素 と配列インデックスを表示します。

私はオンラインの答えを見つけるの本当の問題を抱えています（今のカップルの時間を探して）。

バイナリ検索の仕組みを理解していますが、バイナリ検索できるようにするには配列をソートする必要がありますが、Array.sort関数を使用しないとどうしますか？

誰でもこの問題に取り組むために正しい方向に向けることができますか？

乾杯！

コードは次のとおりです。binarySearchコードは非常に下にあり、 "3"を押すと、私が呼び出している検索部分が中央にあります。

import java.util.ArrayList; 
import java.util.List; 

import javax.swing.JOptionPane; 



public class BirdArrayList { 

    static ArrayList<String> birdList = new ArrayList<String>(5); 
    static String response; 
    static int birdIndex = -1; 

    public static void main(String[]args) 
    { 

     birdList.add("Crow"); //adding five initial birds to the birdList ArrayList 
     birdList.add("Magpie"); 
     birdList.add("Dove"); 
     birdList.add("Finch"); 
     birdList.add("Kookaburra"); 


     while (!"5".equals(response)) 
     { 
      response = JOptionPane.showInputDialog("Please enter the number for what you wish to do \n" 
        + " 1 \t ADD a bird to the list \n" 
        + " 2 \t REMOVE a bird from the list \n" 
        + " 3 \t SEARCH for a bird in the list \n" 
        + " 4 \t DISPLAY the list of birds \n" 
        + " 5 \t QUIT the program"); // Main screen of the program, formatted nicely 

      if(response.equals("1")) // Add a bird 
      { 
       addEntry(); 
      } 

      if(response.equals("2"))//Remove a bird from the list 
      { 
       deleteEntry(); 
      } 

      if(response.equals("3"))//Search for a bird 
      { 
       response = JOptionPane.showInputDialog("Please enter a bird name to SEARCH for it \n and see if it is on the list!"); 
       int birdIndex = (binarySearch(birdList, response)); 
       if(birdIndex >=0) 
       { 
        JOptionPane.showMessageDialog(null, "The bird name " + response + " was on the list " 
          + "\nin Array Index ("+birdIndex+")"); 
       } 
      } 


      if(response.equals("4")) // Displays the array 
      { 
       displayArray(); 
      } 
      if(response.equals("5")) // Quit the program 
      { 
       System.exit(0); 
      } 
     } 

    } 

    public static void addEntry() 
    { 
     response = JOptionPane.showInputDialog("Please enter a bird name to ADD it to the list"); 
     birdList.add(response); // adds the response to the birdList in the next Array position 
     JOptionPane.showMessageDialog(null, response + " added!"); // Shows bird name added 
     displayArray(); 
    } 

    public static void deleteEntry() 
    { 
     response = JOptionPane.showInputDialog("Please enter a bird name to REMOVE it from the list"); 
     boolean isRemoved = false; 
     for(int i=0;i<birdList.size();i++) 
     { 
      if(birdList.get(i).equalsIgnoreCase(response)) 
      { 
       birdList.remove(i); 
       JOptionPane.showMessageDialog(null, response + " removed!"); 
       isRemoved = true; 
      } 

     } 
     if(isRemoved == false) 
     { 
      JOptionPane.showMessageDialog(null, "The bird you tried to remove was not on the list"); 
     } 
     displayArray(); 

     /* How I was originally going to do it before I re-read the requirements. 
     /*if(birdList.contains(response)) 
     { 
      birdList.remove(response); 
      JOptionPane.showMessageDialog(null, response + " removed!"); 
     } 
     else 
     { 
     JOptionPane.showMessageDialog(null, "The bird you tried to remove was not on the list"); 
     }*/ 
    } 
    public static void displayArray() 
    { 
     String displayList = ""; 
     int tempCounter = 0; 
     for(int i=0;i<birdList.size();i++) //Display the ArrayList 
     { 
      String tempBird = birdList.get(i); //Makes tempBird more workable in the displayList formula 2 lines down 
      tempCounter++; // shows a nuber before the bird in the list 
      displayList += tempCounter + ". " + tempBird + "\n"; //formatting nicely  
     } 
      JOptionPane.showMessageDialog(null, displayList); //Displays the list 

    } 

    public static int binarySearch(List<String> birdList, String response) 
    { 
     int low = 0; 
     int high = birdList.size(); 
     int mid = (low + high)/2; 



     while(low<high && !birdList.get(mid).equalsIgnoreCase(response)) 
     { 
      if (birdList.get(mid).equalsIgnoreCase(response)) 
      { 
       low = mid + 1; 
      } 
      else 
      { 
       high = mid - 1; 
      } 

      mid = (low + high)/2; 

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

     } 
     System.out.println("low "+low+"\nhigh " + high + "\nmid " +mid+ "\nBI " +birdIndex); 
     birdIndex = mid; 
     return birdIndex; 
    } 
} 

Answer 1

は、手動で別の文字列が別の「より大きい」「未満」またはであるかどうかを確認するのcompareTo（文字列otherstringは）メソッドを使用して、あなたが望むアルゴリズムの任意の並べ替えを使用して配列をソートすることができます。

あなたが選択ソートアルゴリズムを使用した場合、コードは次のようになります。

// will iterate throughout the entire list to sort 
for (int i = 0; i < birdList.size() - 1; i++) { 
     int lowestVal = i; 

     // will iterate through list to find next smallest value 
     for (int j = i + 1; j < birdList.size(); j++) { 
      if (birdList.get(j).compareTo(birdList.get(lowestVal)) < 0) 
       lowestVal = j; // found new minimum value 
    } 

    // swap out the next lowest value with the next value in the list 
    String temp = birdList.get(i); 
    birdList.set(i, birdList.get(lowestVal)); 
    birdList.set(lowestVal, temp); 
} 

はEDIT：ちょうど少しより多くの情報を。 compareToメソッドは、Stringクラスが実装しているComparableインターフェイスの一部です。これにより、基本的に文字列を比較し、このように並べ替えることができます。