Tìm kiếm nhị phân danh sách C# bằng cách sử dụng điều kiện ủy quyền

Question

Tôi có một số List<T> mà tôi muốn tìm kiếm không cho một mục nhất định mà cho một mục thỏa mãn điều kiện đã cho. Với một mục trong danh sách tôi có thể kiểm tra mà trong 4 điều kiện là đúng:

• các mục mong muốn phải sang trái
• các mục mong muốn phải ở bên phải
• đây là mục mong muốn
• mong muốn không được nằm trong danh sách

Xem lướt qua chức năng danh sách không đáng khích lệ nên tôi tự hỏi liệu có ai biết được chức năng tôi có thể sử dụng không?

Edit: đây là một danh sách tạm thời địa phương vì vậy tôi biết rằng nó sẽ được sắp xếp một cách chính xác

Edit: BinarySearch trông gần như ngay lập nhưng trong trường hợp của tôi, tôi không có một mục để so sánh với. Tôi muốn sử dụng giải pháp của Jon Skeet và bỏ qua một arg, nhưng tôi không chắc chắn rằng tôi có thể tin tưởng vào nó luôn luôn là cùng một arg.

Answer 1

Chỉnh sửa mới: Tôi sẽ để lại các tìm kiếm nhị phân bổ sung bên dưới, vì chúng hữu ích cho người khác và đây là tùy chọn cuối cùng mà tôi nghĩ bạn thực sự muốn gì. Người được ủy quyền của bạn phải trả về số dương nếu mục mà nó tìm kiếm "nhỏ hơn" số được chỉ định, số âm nếu số đó lớn hơn số được chỉ định và 0 nếu nó vừa phải.

public static int BinarySearchForMatch<T>(this IList<T> list, 
    Func<T,int> comparer) 
{ 
    int min = 0; 
    int max = list.Count-1; 

    while (min <= max) 
    { 
     int mid = (min + max)/2; 
     int comparison = comparer(list[mid]); 
     if (comparison == 0) 
     { 
      return mid; 
     } 
     if (comparison < 0) 
     { 
      min = mid+1; 
     } 
     else 
     { 
      max = mid-1; 
     } 
    } 
    return ~min; 
} 

Cũ chỉnh sửa: Tôi sẽ để lại câu trả lời ban đầu dưới đây, nhưng đây là hai lựa chọn khác.

Cách đầu tiên lấy một phép chiếu từ dữ liệu nguồn sang loại khóa và chỉ định khóa cần tìm. Việc so sánh chính nó chỉ được thực hiện theo cách mặc định cho loại khóa đó:

public static int BinarySearchBy<TSource,TKey>(this IList<TSource> list, 
    Func<TSource,TKey> projection, TKey key) 
{ 
    int min = 0; 
    int max = list.Count-1; 

    while (min <= max) 
    { 
     int mid = (min + max)/2; 
     TKey midKey = projection(list[mid]); 
     int comparison = Comparer<TKey>.Default.Compare(midKey, key); 
     if (comparison == 0) 
     { 
      return mid; 
     } 
     if (comparison < 0) 
     { 
      min = mid+1; 
     } 
     else 
     { 
      max = mid-1; 
     } 
    } 
    return ~min; 
} 

Thứ hai thay thế một Func, để so sánh một mục từ danh sách với khóa mà chúng tôi đang tìm kiếm. Mã này là gần như giống hệt nhau, tất nhiên - nó chỉ là sự so sánh mà thay đổi:

public static int BinarySearchBy<TSource,TKey>(this IList<TSource> list, 
    Func<TSource,TKey,int> comparer, TKey key) 
{ 
    int min = 0; 
    int max = list.Count-1; 

    while (min <= max) 
    { 
     int mid = (min + max)/2; 
     int comparison = comparer(list[mid], key); 
     if (comparison == 0) 
     { 
      return mid; 
     } 
     if (comparison < 0) 
     { 
      min = mid+1; 
     } 
     else 
     { 
      max = mid-1; 
     } 
    } 
    return ~min; 
} 

Cả hai đều chưa được kiểm tra, nhưng ít nhất biên dịch :)

Original câu trả lời:

Bạn có thể sử dụng List<T>.BinarySearch với số IComparer<T>.Bạn không phải tự mình thực hiện IComparer<T> - Tôi đã tham gia vào số MiscUtil tạo số IComparer<T> từ đại biểu Comparison<T>. Điều đó chỉ phát hiện ra ba điều kiện đầu tiên, nhưng tìm kiếm nhị phân sẽ tìm ra điều kiện cuối cùng từ những điều kiện còn lại.

Thực tế, mã quá ngắn nên tôi cũng có thể dán mã đó vào đây (không có ý kiến, thừa nhận).

public sealed class ComparisonComparer<T> : IComparer<T> 
{ 
    readonly Comparison<T> comparison; 

    public ComparisonComparer(Comparison<T> comparison) 
    { 
     if (comparison == null) 
     { 
      throw new ArgumentNullException("comparison"); 
     } 
     this.comparison = comparison; 
    } 

    public int Compare(T x, T y) 
    { 
     return comparison(x, y); 
    } 
} 

Vì vậy, bạn có thể làm điều gì đó như:

var comparer = new ComparisonComparer<Person>((p1, p2) => p1.ID.CompareTo(p2.ID)); 
int index = list.BinarySearch(employee, comparer); 

MiscUtil cũng có một ProjectionComparer bạn có thể quan tâm - bạn chỉ định một chiếu, giống như trong OrderBy với LINQ - nhưng nó thực sự phụ thuộc vào trường hợp sử dụng của bạn.

Answer 2

Bạn có chắc chắn về những điều kiện đó không? Thông thường hoạt động nếu danh sách được sắp xếp, trong trường hợp này có lẽ bạn muốn sử dụng một số SortedList<TKey, TValue> ngay từ đầu.

Dù bằng cách nào, giả sử C# 3.0 hoặc sau đó bạn có thể muốn phương thức .Where(). Viết trong tình trạng của bạn như một Lambda và để cho khung làm việc tìm kiếm. Nó nên sử dụng một kỹ thuật tìm kiếm phù hợp với bộ sưu tập.

Answer 3

Bạn có thể muốn triển khai nó trong một trình so sánh tùy chỉnh cho đối tượng của bạn (được gọi là so sánh trong C# tài liệu).