쌍 목록을 통한 이진 검색

Question

element과 일치하는 elem을 찾아야합니다.
내 프로그램이 작동하지만 효율적이지 않습니다. 나는 매우 큰 ArrayList<Obj> pairs (4000 개가 넘는 요소들)을 가지고 있고 나는 이진 검색을 사용하여 일치하는 색인을 찾는다. 새로운 ArrayList를 목록으로 ArrayList를 쌍의 절반을 복사하는 루프를 사용하는 것보다 더 효율적인 방법이 있는지

public int search(String element) { 
    ArrayList<String> list = new ArrayList<String>(); 
    for (int i = 0; i < pairs.size(); i++) { 
     list.add(pairs.get(i).getElem()); 
    } 
    return index = Collections.binarySearch(list, element); 
} 

이 궁금하다. 확대 개체에 대한 생성자 : Obj x = new Obj(String elem, String word);

Answer 1

문제가 해결 된 것처럼 보입니다. ArrayList 쌍 형식이 Obj이고 element 형식이 String 인 경우 Collections.binarySearch를 사용할 수 없기 때문에 새 변수 Obj x = new Obj(element, "");을 만들기로 결정했습니다. 내 compareTo 메서드가 두 elem을 비교하고 Obj x의 두 번째 변수를 무시하므로 문자열에 문제가 발생하지 않은 것 같습니다 (내 JUnit 테스트를 통과했습니다).

내 업데이트 방법 :

public int search(String element) { 
    Obj x = new Obj(element, ""); 
    int index = Collections.binarySearch(pairs, x); 

Answer 2

마스터 목록 (pairs는) 다음 변경되지 않으면 나는 예를 들어 index 구조, 역 유지하기 위해 TreeMap을 만드는 것을 권 해드립니다 : 요소를 검색하는 동안,

List<String> pairs = new ArrayList<String>(); //list containing 4000 entries 

Map<String, Integer> indexMap = new TreeMap<>(); 

int index = 0; 
for(String element : pairs){ 
    indexMap.put(element, index++); 
} 

지금을 , 당신이 할 필요가있다 :

indexMap.get(element); 

요소가 전자를하지 않는 경우 당신에게 필요한 index 또는 null을 줄 것이다 xist. 또한 요소가 목록에 여러 번 나타날 수있는 경우 indexMap을 Map<String, List<Integer>>으로 변경할 수 있습니다.

은 현재 알고리즘 반복 목록과 이진 검색을 호출하므로 복잡성은 반복에 대해 O(n) 것 및 O(log n) 시간 비용을 log(n) 보장 TreeMap 반면에 훨씬 더 빨리 할 수 ​​있도록.

Here의 설명서는 TreeMap입니다.