C# 이진 검색 변형

Question

목록이 정렬됩니다.

나는리스트를 가지고 있고 그것에 바이너리 검색을하고 싶다. T는 StartIndex, EndIndex 등과 같은 멤버가 있습니다.

StartIndex를 사용하여 목록에서 이진 검색을 할 수 있습니다.이를 위해 IComparable을 구현했습니다.

다음과 같이 약간 뒤틀 필요가 있습니다. OffBy 값이 작은 StartIndex를 찾고 싶습니다. 예를 들어

: T.StartIndex = 100

입력이 101이고 OffBy 한 후 BinarySearch이 객체를 리턴할지.

어떻게하면됩니까?

나는 목록에있는 기본 binarysearch 메서드로 어떻게 이런 질문을합니다. 그건 내가 관심있는 것이지, 커스텀 바이너리 검색 구현에는 관심이 없다.

Answer 1

List<T>.BinarySearch을 사용하는 경우 정확한 위치를 찾거나 항목을 삽입해야하는 인덱스의 비트 보수를 반환합니다.

그래서 음수를 반환하면 다음 항목과 이전 항목 (물론 끝을주의 깊게 살펴보십시오) 중 어느 항목이 원하는 허용 오차 내에 있는지 확인하십시오. 예를 들어

:

int index = list.BinarySearch(item); 
if (index < 0) 
{ 
    int candidate = ~index; 
    if (candidate > 0 && 
     Math.Abs(list[candidate - 1].StartIndex - item.StartIndex) <= tolerance) 
    { 
     index = candidate - 1; 
    } 
    else if (candidate < list.Count - 1 && 
     Math.Abs(list[candidate + 1].StartIndex - item.StartIndex) <= tolerance) 
    { 
     index = candidate + 1; 
    } 
    else 
    { 
     // Do whatever you need to in the failure case 
    } 
} 
// By now, index is correct