일부 값 뒤에있는 목록에서 가장 작은 요소 검색

Question

정수 목록 <1,5,10> (오름차순으로 정렬 된 것으로 가정)을 고려하십시오.

숫자가 key = 6 인 경우, key (이 경우 10이 될 것입니다.) 뒤에 가장 작은 요소를 반환하는 유틸리티 메서드가 있습니까?

주의 : 목록의 요소를 통해 반복하고 key과 비교하면 할 수있는 확실한 방법이지만, 같은 일 :

Answer 1

이진 검색이 작동하지만, 사실 당신이 값의 정렬 설정 한 다음 대신 List하는 SortedSet (또는 더 나은 NavigableSet)가있는 경우, 선택의 가장 자연스러운 데이터 구조입니다.

다음은 사용 예입니다 :

NavigableSet<Integer> nums = new TreeSet<Integer>(
     Arrays.asList(9,1,5,7,3) 
    ); 

    System.out.println(nums); // "[1, 3, 5, 7, 9]" 

    System.out.println(nums.first()); // "1" 
    System.out.println(nums.last()); // "9" 

    System.out.println(nums.higher(3)); // "5" 
    System.out.println(nums.lower(8)); // "7" 

    System.out.println(nums.subSet(2,8)); // "[3, 5, 7]" 
    System.out.println(nums.subSet(1, true, 5, true)); // "[1, 3, 5]" 

더욱 유용한 몇 가지 시나리오가 될 수 NavigableMap 대응도있다.

Answer 2

가지고 할 수있는 유틸리티 방법이 존재하는 경우 난 그냥 궁금하네요 당신은 Binary Search을 고려 했습니까? Collections에는 사용할 수있는 binarySearch 메소드가 있습니다.

반환 값 : 컬렉션 binarySearch 문서에서

검색 키의 인덱스,이 목록에 포함되어 경우; (- (삽입 점) - 1). 리스트의 모든 요소 이 경우, 키는 list.size()보다 큰 첫번째 요소의 인덱스 : 삽입 지점 키 리스트에 삽입 할 때의 포인트이다 지정된 키보다 작습니다. 이 은 키가 인 경우에만 이> = 0이되도록 보장합니다.

필요한 답변을 얻기 위해 Collections.binarySearch의 반환 값을 사용하는 방법을 알아 보겠습니다.