리스트가 정렬 될 때리스트에서 값을 찾는 가장 좋은 방법

Question

Java ArrayList가 있다고 가정 해 봅시다. 이제 x 값의 인덱스를 찾고 싶습니다. 이 작업을 수행하는 가장 빠른 방법은 무엇입니까? IndexOf() 메서드 사용? 간단한 for 루프의 모든 값을 반복할까요? 멋진 알고리즘 사용? 우리는 약 50 개의 정수형 키에 대해 이야기하고 있습니다.

Answer 1

Binary search하지만 50 개 항목이므로 누가 신경 써야합니까? 단순 선형 검색은 더 간단하며 50 개 항목의 성능 차이는 미미합니다.

편집 : 기본 제공 java.util.Collections binarySearch 메서드를 사용할 수도 있습니다. 해당 항목을 찾을 수없는 경우에도 삽입 포인터가 반환됩니다. 아이템이 실제로 원하는 것인지 확인하기 위해 여분의 수표를 만들어야 할 수도 있습니다. 포인터 @Matthew에게 감사드립니다.

Answer 2

tvanfosson이 맞습니다. 그 중 하나의 시간은 매우 낮으므로이 코드가 자주 실행되지 않는 한 별 차이가 없습니다.

그러나 Java에는 목록 (ArrayList 포함) Collections.binarySearch의 이진 검색 기능이 기본 제공됩니다.

Answer 3

키가 허용되는 분포이면 Interpolation Search은 실행 시간을 고려하면 매우 빠릅니다.

코딩 시간을 고려하면 IndexOf()입니다 (또는 C#을 사용하고 Java를 모르지만) 데이터 유형에 사용할 수있는 경우 이진 검색을 내장 할 수 있습니다.

Answer 4

import java.util.ArrayList; 
import java.util.Collections; 

ArrayList myList = new ArrayList(); 
// ...fill with values 

Collections.sort(myList); 
int index = Collections.binarySearch(myList, "searchVal"); 

편집 : 테스트되지 않은 코드