컬렉션에 대해 키를 검색하고 존재하지 않는 경우 다음으로 높은 항목을 얻는 방법은 무엇입니까?

Question

.NET에서 정렬 된 컬렉션을 검색하여 인덱스를 가져 오거나 인덱스가없는 경우의 인덱스를 얻으시겠습니까?

예를 들어 요소 {1,5,8,10}을 포함하는 목록이 있습니다. 나는 7을 찾는다. 존재하지 않지만 그 다음으로 높은 키는 의 색인을 갖는 8이다.

예 :

SortedList<int, int> list = new SortedList<int, int>(); 
list.Add(1, 1); 
list.Add(5, 1); 
list.Add(8, 1); 
list.Add(10, 1); 

int index = list.IndexOfKeyOrNext(7); // theoretical function. returns 2 

나는 7시에 임시 항목을 추가하여이 작업을 수행 할 수 있습니다, list.IndexOfKey를 호출 (7), 다음 내 임시 항목을 제거. 그러나 이것은 느립니다. 더 좋은 방법이 있습니까?

편집 : 내 목록이 정렬됩니다.

Answer 1

수정 된 이진 검색이 가장 빠릅니다. 바이너리 검색은 O (로그 n) 연산이므로 일치하는 항목을 찾기 위해 모든 항목을 반복하는 것보다 훨씬 빠릅니다.

public int IndexOfKeyOrNext(SortedList<int,int> list, int find) { 
    int first = 0; 
    int last = list.Count - 1; 
    while (first < last) { 
     int pos = first + last/2; 
     if (list.Keys[pos].Key < find) { 
     first = pos + 1; 
     } else { 
     last = pos; 
     } 
    } 
    if (first < list.Count && list.Keys[first] >= find) { 
     return first; 
    } else { 
     return -1; 
    } 
} 

Answer 2

정렬 된 목록에만이 작업을 수행하는 경우 Binary Search algorithm의 사용자 지정 변형을 사용하는 것이 좋습니다. 원하는 요소를 찾지 못하면 실제로 상한값에 목록의 다음 항목. 당신의 예에서

, 알고리즘은 (1 ~ 10)을 찾고되지 않습니다 어떤

lowerBound = 0 
upperBound = 3 

둘 인덱스 값으로 시작합니다. 따라서 두 반쪽 0, 1 및 2, 3 - 을 확인하려고합니다. 표준 알고리즘을 수정하는 곳입니다. 둘 다 같지 않으므로 두 번째 절반의 첫 번째 요소가 다음 큰 항목이라고 가정 할 수 있습니다 그 인덱스는 후반 (2)의 하한입니다.

이렇게하면 O (log (n))의 효율성을 얻을 수 있습니다.

Answer 3

int yourValue = 5; 

var item = list.FirstOrDefault(x => x >= yourValue); 

if(item != null) 
{ 
    var index = list.IndexOf(item); 
} 

귀하의 목록이 사전 정렬되어 있고 Linq를 사용할 수 있다고 가정합니다.

Answer 4

SortedList 대신 List<T>을 사용하고 있고 정렬되어 있는지 확인하려면 BinarySearch 메서드를 사용하면됩니다.

요소의 인덱스 또는 비트 보수가있는 경우 값을 찾을 수있는 인덱스로 반환합니다. 이것을 사용하여 다음으로 높은 요소를 찾을 수 있습니다. 코드는 다음과 같습니다.

var index = list.BinarySearch(7); 
if (index >= 0) { 
    Console.WriteLine("found value"); 
} else { 
    Console.WriteLine("next value is {0}", list[~index + 1]); 
}