Как я могу сделать бинарный поиск по массиву структур с конкретным значением поля в C #?

Question

У меня есть массив структур, где структура имеет три целочисленных поля.Он отсортирован по одному из полей, скажем, F, и я хочу, чтобы был выполнен двоичный поиск по этому полю, то есть функция вида binarySearch (mystruct [] myarray, int val), которая возвращает индексструктуры, в которой поле F = val.Я знаю, что существует функция Array.BinarySearch (массив T [], значение T), но она позволяет только искать тип T, который совпадает с типами в массиве.Это означает, что если я хочу выполнить поиск по значению, мне нужно создать новую структуру и установить для поля F это значение, чтобы я мог передать его этой функции.Я не думаю, что это приведет к значительным потерям производительности, но это выглядит ужасно.Другой способ, которым я могу мыслить, - реализовать эту функцию самостоятельно, но это также кажется неэффектным, когда существует нечто подобное.Любые предложения для лучшего пути или какой путь будет предпочтительным?

Answer 1

Вы можете либо реализовать IComparable<T> для своей структуры для сравнения в поле (F), либо вы можете создать IComparer<> для своей структуры, которая будет сравнивать на основе этого поля и передавать ее в Array.BinarySearch().

Так что либо:

// using IComparable<T>
public struct MyStruct : IComparable<MyStruct>
{
    public int F { get; set; }

    // other fields that should not affect "search"
    public int X { get; set; }

    public int CompareTo(MyStruct other)
    {
        return F.CompareTo(other.F);
    }
}

Что можно назвать:

MyStruct target = new MyStruct { F = 13 };

Array.BinarySearch(arrayOfMyStruct, target);

Или отдельный IComparer<MyStruct>:

public struct MyStruct 
{
    public int F { get; set; }

    // other non-sort/search affecting properties
    public int X { get; set; }
}

public struct MyStructComparer : IComparer<MyStruct>
{
    public int Compare(MyStruct x, MyStruct y)
    {
        return x.F.CompareTo(y.F);
    }
}

Что можно назвать как:

MyStruct target { F = 13; }

Array.BinarySearch(myArrayOfStruct, target, new MyStructComparer());

Первый имеет меньше кода, но он сильно связывает порядок с типом, что, если вы хотите изменить порядок в зависимости от ситуации (то есть разрешить несколько порядков сортировки), это не идеально. Последний дает больше гибкости в том, что вы можете предоставить несколько различных заказов независимо от структуры, но для этого требуется дополнительный класс.

UPDATE

Если вы не хотите создавать структуру dummy для сравнения, вы можете реализовать IComparable, например:

public struct MyStruct : IComparable
{
    public int F { get; set; }

    // other non-sort/search affecting properties
    public int X { get; set; }

    public int CompareTo(object other)
    {
        // if the type is NOT an int, you can decide whether you'd prefer
        // to throw, but the concept of comparing the struct to something
        // unknown shouldn't return a value, should probably throw.
        return F.CompareTo((int)other);
    }
}

Что можно назвать как:

Array.BinarySearch(arrayOfMyStruct, 13);

Но, опять же, это сильно связывает вашу реализацию класса с данным типом сравнения, что, на мой взгляд, более утомительно, чем использование фиктивной цели поиска, но это мое личное предпочтение. Лично, особенно с таким коротким синтаксисом инициализатора, я предпочитаю использовать фиктивную цель:

var target = new MyStruct { F = 13 };

ОБНОВЛЕНИЕ : Вы можете поддерживать как int, так и MyStruct сравнений, но это быстро запутывается, поэтому я лично рекомендую снова использовать фиктивную структуру, чтобы избежать головной боли:

// implement IComparable<int> for the int search (w/o dummy), and IComparable<MyStruct> for sort
public struct MyStruct : IComparable, IComparable<MyStruct>, IComparable<int>
{
    public int F { get; set; }

    // other non-sort/search affecting properties
    public int X { get; set; }

    public int CompareTo(object other)
    {
        if (other is int) 
            return F.CompareTo((int)other);

        if (other is MyStruct)
            return F.CompareTo((MyStruct)other);

        throw new InvalidOperationException("Other must be int or MyStruct.");
    }

    public int CompareTo(MyStruct other)
    {
        return F.CompareTo(other.F);
    }

    public int CompareTo(int other)
    {
        return F.CompareTo(other);
    }
}

Answer 2

Если ваша структура реализует IComparable, вы можете использовать:

// myValue is an the value of the field to compare to
Array.BinarySearch(myArray, myValue);

, как описано в http://msdn.microsoft.com/en-us/library/y15ef976.aspx

Вы можете сравнить структуру с объектом с помощью IComparable, чтобы вы могли передатьзначение intead новой структуры.В вашей реализации CompareTo вы можете сравнить любое значение со значением поля, что позволит вам сказать «Моя структура должна считаться больше / меньше этого числа».

РЕДАКТИРОВАТЬ:

ЗдесьПример CompareTo для вашей структуры:

public int CompareTo(object obj)
{
    if (obj is int)
    {
        return myIntField.CompareTo((int)obj);
    }
    return 0;
}

Answer 3

Один из способов - создать пользовательский IComparer<T>, который сравнивает экземпляры вашей структуры на основе только значения этого поля и передает его в эту перегрузку из BinarySearch (вам также потребуется создайте "фиктивный" экземпляр структуры для сравнения). Это, наверное, самое чистое решение.

Однако на практике вы можете использовать LINQ для проецирования в коллекцию значений полей и двоичного поиска в них; результирующий индекс будет таким же, как если бы вы искали саму коллекцию структур. Например:

var structs = new MyStruct[n];
var index = structs.Select(i => i.F).ToList().BinarySearch(42);

В приведенном выше коде F - это имя поля, а 42 - это значение, которое вы ищете (его типом будет тип F). Это не будет так быстро, но вам не нужно писать какой-либо код, и скорость вполне может быть неуместна в вашем случае.

Обновление: Чтобы уточнить: очевидно, что приведенный выше код будет O (n) из-за операции проецирования, поэтому использование бинарного поиска один раз после проецирования, как это глупо (вы можете просто сделать линейный поиск вместо ). Однако, если вы намереваетесь сделать многократный поиск , это может начать иметь смысл.

Я бы определенно не рекомендовал переопределять Equals в вашей структуре, если только сравнение между экземплярами не должно сводиться к сравнению F членов везде в вашем приложении .