java : 비교기가있는이 binarySearch가 작동하지 않는 이유는 무엇입니까?

Question

Updated : Collections.sort()를 사용하여 comparator 매개 변수로 arrayList를 정렬하려고합니다. 그런 다음 binarysearch를 수행하십시오.

package collection; 

import java.util.*; 

public class TryBinarySearch { 
    public static void main(String[] args){ 
     List<Integer> list = new ArrayList<>(); 
     for (int i = 0; i < 100; i++) 
      list.add(i); 
     System.out.println(list); 
     int b = Collections.binarySearch(list, 8); 
     System.out.println(b); // a is 8 as expected. 

     Collections.shuffle(list); 
     System.out.println(list); 

     Collections.sort(list, new 
       Comparator<Integer>(){ 
      public int compare(Integer a, Integer b){ 
       return b.intValue() - a.intValue(); 
      } 
     }); 
     System.out.println(list); //list is reversed as expected. 
     int a = Collections.binarySearch(list, 8); 
     System.out.println(a); // why a is -1? 
    } 
} 

b는 예상대로 8이다. 역순으로 정렬했습니다. 제 질문은 왜 a가 92 대신에 -1 인지요?

Answer 1

목록을 섞어서 정렬하지 않았습니다. 이진 검색을 수행하려면 정렬 된 목록이 있어야합니다.

Answer 2

이진 검색을 수행하려면 목록을 정렬해야합니다. 처음에 목록을 섞어서 전제 조건 인 Collections.binarySearch을 무효화했습니다.

목록

이 호출하기 전에, (정렬 (목록, 비교기)와 같은 방법에 의해) 지정된 콤퍼레이터에 따라 오름차순으로 정렬되어야한다. 정렬되지 않은 경우 결과는 정의되지 않습니다.

알고리즘은 정렬되는 목록에 의존합니다. 따라서 나중에 정렬 할 때 binarySearch이 작동합니다.

Answer 3

이진 검색은 검색하려는 목록에 따라 다릅니다. 당신은 분명히 당신의 것을 걷고 있습니다. 을으로 정렬 하시겠습니까? Comparator을 대신 사용 하시겠습니까?

Answer 4

이진 검색은 목록이 이미 정렬 된 경우에만 작동합니다. 이진 검색이 작동하는 방식은 "추측"색인의 값이 우리가 찾고있는 것보다 높으면 실제 색인이 낮아야하며 그 반대의 경우도 알고리즘이 가정한다고 가정합니다.

컬렉션이 정렬되지 않으면 해당 가정이 유지되지 않으므로 알고리즘이 실패합니다.

documentation 상태 매우 명확 :

목록은합니다 (sort(List, Comparator) 방법 등에 의해) 지정된 콤퍼레이터에 따라 오름차순으로 정렬되어야 호출하기 전에. 정렬되지 않은 경우 결과는 정의되지 않습니다.

Answer 5

binarySearch(list, key) 호출의 문서는 말한다 :

목록은

귀하의 목록에있는 사용자 정의 Comparator을 사용하여 정렬하고, 그러므로 자연 순서에 따라 오름차순으로 정렬한다 검색 알고리즘을 나타 내기 위해 호출에 전달해야합니다. 항목 비교 방법 :

이 호출 0

는 문서는 말한다 :

목록은 그래서, 지금 당신이 질문을 개편 한 지정된 콤퍼레이터