Variation de recherche binaire C#

Question

La liste est triée.

J'ai une liste et j'aimerais faire une recherche binaire dessus. T a des membres comme StartIndex, EndIndex etc.

Je peux faire une recherche binaire sur la liste avec StartIndex, c'est-à-dire: J'ai implémenté IComparable pour cela.

J'ai besoin de tordre ceci un peu comme suit: Je veux trouver un StartIndex qui pourrait être OffBy une petite valeur.

Par exemple: T.StartIndex = 100

si l'entrée est 101 et 1 OffBy alors BinarySearch doit retourner cet objet.

Comment est-ce que je peux faire ceci? BTW, je demande comment cela avec la méthode binarysearch par défaut que List a. C'est ce que je suis intéressé, pas intéressé par une implémentation de recherche binaire personnalisée.

Answer 1

Si vous utilisez List<T>.BinarySearch alors il trouvera la position exacte d'un existe, ou retourner le complément au niveau du bit de l'index auquel vous auriez besoin d'insérer l'élément.

Donc, si elle retourne un nombre négatif, il suffit de vérifier les éléments suivants et précédents (en faisant attention aux extrémités bien sûr) pour voir si l'un ou l'autre est dans votre tolérance souhaitée.

Par exemple:

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