Бинарный поиск со строками

Question

У меня есть массив объектов, и я хочу найти свойство date/day (пользователь решает) с помощью двоичного поиска.

** EDIT: Я прочитал значения SharesArray [mid] .Date (и дневные значения) из текстового файла и примеры: 05/02/2015, 14/10/2014. Значение searchString будет получено из пользователь, но будет в том же формате, что и значения даты. **

Это моя первая попытка, так что я просто пытаюсь свойство даты:

int high, low, mid; 
high = SharesArray.Length - 1; 
low = 0; 

while (low <= high) 
{ 
    mid = (low + high)/2; 
    if (String.Compare(SharesArray[mid].Date, searchString, true) == 0) 
    { 
     break; 
    } 
    else if (String.Compare(SharesArray[mid].Date, searchString, true) > 0) 
    { 
     high = mid - 1; 
    } 
    else if (String.Compare(SharesArray[mid].Date, searchString, true) < 0) 
    { 
     low = mid + 1; 
    } 

Я также попробовал последний еще, если заявление, как только еще и что не делает никакой разницы.

Кроме того, имеет значение, каков круг круглых строк1 и string2 в части String.Compare?

Answer 1

Резюмируя ответ от Q & А в комментариях к вопросу, с небольшим количеством дополнительного контекста.

Для бинарного поиска, есть несколько компонентов, которые нужно заботиться о

1. Входной массив бинарной функции поиска должны быть рассортированы.
2. Учитывая алгоритм, который вы реализовали, они должны быть отсортированы в порядке возрастания.
3. Вы должны иметь функцию сравнения трехпозиционный, что для compare(lhs, rhs) возвращений: < 0 если lhs < rhs, > 0 если lhs > rhs и 0 если lhs == rhs.
4. Порядок аргументов в функции compare имеет значение, если вы их переключите, вы будете использовать неправильную ветку и изменить верхнюю границу поиска вместо нижней или наоборот.
5. Для вашей реализации у вас был порядок с lhs: SharesArray[mid].Date и rhs = searchString.
6. Поскольку вы сравниваете даты, вам необходимо использовать функцию DateTime.Compare и конвертировать ваши строки даты в DateTime экземпляры, используя DateTime.ParseExact(myString, "dd/MM/yyyy", CultureInfo.InvariantCulture);. При сравнении строк вы получите неправильные результаты, такие как "05/02/2015" < "14/10/2014".

И, наконец, еще один анекдотический замечание сделать (см here):

Расчет величины поворота mid восприимчив к целому числу переполнение. Если рассчитать его как

mid = (low + high)/2; 

тогда low + high может стать больше, чем припадков в виде целого числа.

Предпочтительный способ расчета mid поэтому

`mid = low + ((high - low) >> 1);`. 

Answer 2

Рассматривали ли вы LINQ?

var searchIndex = SharesArray 
    .Select(s => s.Date) 
    .ToList() 
    .BinarySearch(searchString);