Реализация моего собственного метода Collections.binarySearch

Question

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

Что делает мой код прямо сейчас, используется Collections.binarySearch, чтобы найти номера телефонов или найти имена. Тем не менее, мне было интересно, как я могу реализовать свой собственный бинарный поиск, поскольку эта глава в основном представляет собой введение в поиск и сортировку, поэтому я решил, что узнаю больше об этом.

Вот важные части моего кода

Здесь я использую интерфейс comparable

public int compareTo(Item otherObject) 
    { 
     Item other = (Item) otherObject; 
     return key.compareTo(other.key); 
    } 

Я тогда Добавить телефонные номера и имена в ArrayLists через

// Read a line containing the name 
     String name = in.nextLine(); 
     // Read a line containing the number 
     String number = in.nextLine(); 
     // Store the name and number in the byName array list 
     byName.add(new Item(name, number)); 
     // Store the number and name in the byNumber array list 
     byNumber.add(new Item(number, name)); 

, а затем вызвать другой метод, который делает

int index = Collections.binarySearch(byName, new Item(k,"")); 
    if(index<0) return null; 
    return byName.get(index).getValue(); 

У меня также есть другие способы поиска: byPhone

Таким образом, все находилось правильно.

Мой вопрос

То, что я хочу знать, как я могу реализовать свой собственный метод, который будет делать BinarySearch. Я выполнил двоичный поиск только для массивов и поиска числа в массиве, но у меня возникают трудности с пониманием того, как будет настроен метод, поскольку мы имеем дело с объектами и списками массивов.

Например, я хотел сделать этот метод следующим образом:

int myBinarySearch(ArrayList<Item> thisItem, Object Item) 
    { 
      // search logic here 
    } 

Однако я не уверен, является ли это правильный подход. Мог бы кто-нибудь объяснить мне, как именно я должен форматировать свой метод для двоичного поиска, учитывая тот факт, что у меня есть куча объектов в arraylist, которые нужно сортировать, а не простой массив.

В настоящее время рабочий код

Вот полный код для моего в настоящее время работает с использованием метода Collections.binarySearch

/Item.java: 

/** 
    An item with a key and a value. 
*/ 
public class Item implements Comparable<Item> 
{ 
    private String key; 
    private String value; 
    /** 
     Constructs an Item object. 
     @param k the key string 
     @param v the value of the item 
    */ 
    public Item(String k, String v) 
    { 
     key = k; 
     value = v; 
    } 
    /** 
     Gets the key. 
     @return the key 
    */ 
    public String getKey() 
    { 
     return key; 
    } 
    /** 
     Gets the value. 
     @return the value 
    */ 
    public String getValue() 
    { 
     return value; 
    } 
    public int compareTo(Item otherObject) 
    { 
     Item other = (Item) otherObject; 
     return key.compareTo(other.key); 
    } 
} 

//LookupTable.java: 

import java.util.ArrayList; 
import java.util.Collections; 
import java.util.Scanner; 
/** 
    A table for lookups and reverse lookups 
*/ 
public class LookupTable 
{ 
    private ArrayList<Item> byName; 
    private ArrayList<Item> byNumber; 
    /** 
     Constructs a LookupTable object. 
    */ 
    public LookupTable() 
    { 
     byName = new ArrayList<Item>(); 
     byNumber = new ArrayList<Item>(); 
    } 
    /** 
     Reads name and number pairs from the Scanner 
     and adds them to the byName and byNumber array lists. 
     @param in the scanner for reading the input 
    */ 
    public void read(Scanner in) 
    { 
     while (in.hasNextLine()) 
     { 
     // Read a line containing the name 
     String name = in.nextLine(); 
     // Read a line containing the number 
     String number = in.nextLine(); 
     // Store the name and number in the byName array list 
     byName.add(new Item(name, number)); 
     // Store the number and name in the byNumber array list 
     byNumber.add(new Item(number, name)); 
     } 
     // Sort the byName Items so we can binary search 
     Collections.sort(byName); 
     // Sort the byNumber Items so we can binary search 
     Collections.sort(byNumber); 
    } 
    /** 
     Looks up an item in the table. 
     @param k the key to find 
     @return the value with the given key, or null if no 
     such item was found. 
    */ 
    public String lookup(String k) 
    { 
     // Use the Collections.binarySearch() method to find the 
     // position of the matching name in the byName array list. 
     // Return null if position is less than 0 (not found). 
     // Otherwise, return the number for the found name. 
    int index = Collections.binarySearch(byName, new Item(k,"")); 
    if(index<0) return null; 
    return byName.get(index).getValue(); 
    } 
    /** 
     Looks up an item in the table. 
     @param v the value to find 
     @return the key with the given value, or null if no 
     such item was found. 
    */ 
    public String reverseLookup(String v) 
    { 
     // Use the Collections.binarySearch() method to find the 
     // position of the matching number in the byNumber array list. 
     // Return null if position is less than 0 (not found). 
     // Otherwise, return the name for the found number. 
    int index = Collections.binarySearch(byNumber, new Item(v, "")); 
    if(index<0) return null; 
    return byNumber.get(index).getValue(); 
    } 
} 

//PhoneLookup.java: 

import java.io.IOException; 
import java.io.FileReader; 
import java.util.Scanner; 
/* The input file has the format 
Abbott, Amy 
408-924-1669 
Abeyta, Ric 
408-924-2185 
Abrams, Arthur 
408-924-6120 
Abriam-Yago, Kathy 
408-924-3159 
Accardo, Dan 
408-924-2236 
Acevedo, Elvira 
408-924-5200 
Acevedo, Gloria 
408-924-6556 
Achtenhagen, Stephen 
408-924-3522 
. . . 
*/ 
public class PhoneLookup 
{ 
    public static void main(String[] args) throws IOException 
    { 
     Scanner in = new Scanner(System.in); 
     System.out.println("Enter the name of the phonebook file: "); 
     String fileName = in.nextLine(); 
     LookupTable table = new LookupTable(); 
     FileReader reader = new FileReader(fileName); 
     table.read(new Scanner(reader)); 
     boolean more = true; 
     while (more) 
     { 
     System.out.println("Lookup N)ame, P)hone number, Q)uit?"); 
     String cmd = in.nextLine(); 
     if (cmd.equalsIgnoreCase("Q")) 
      more = false; 
     else if (cmd.equalsIgnoreCase("N")) 
     { 
      System.out.println("Enter name:"); 
      String n = in.nextLine(); 
      System.out.println("Phone number: " + table.lookup(n)); 
     } 
     else if (cmd.equalsIgnoreCase("P")) 
     { 
      System.out.println("Enter phone number:"); 
      String n = in.nextLine(); 
      System.out.println("Name: " + table.reverseLookup(n)); 
     } 
     } 
    } 
} 

Answer 1

Вы можете найти, как JDK делает его из исходного кода JDK. В java.util.Collections:

private static <T> 
    int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) 

Очень же, как тот, с которым вы работаете.

Answer 2

Бинарный поиск - очень простой алгоритм. В псевдокоде это:

find(list, item): 
    if list is empty 
     return not found 
    get middle item from list 
    if item matches middle 
     return middle 
    else if item is before middle 
     return find(list before middle, item) 
    else 
     return find(list after middle, item) 

Список должен быть отсортирован, чтобы это могло работать. Вы можете использовать List.subList, чтобы избежать необходимости копировать или пропускать индексы.

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