Бинарный поиск строки в массиве байт на C#

Не понятно зачем вы переводите строку в байты, вы ведь вполне можете работать и с массивом объектов, все точно так же как с числовыми значениями, только сравниваете "Имя" например: array[index].Name > targetName строки IComparable, так что их можно сравнить на больше меньше используя метод CompareTo()

В самом простом виде поиск будет выглядеть так:

public static User BinarySearch(User[] array, string targetName) => BinarySearch(0, array.Length -1, array, target);
static User BinarySearch(int left, int right, User[] array, string targetName)
{
    if (right - left < 0) throw new Exception($"{targetName} не найден");
    var index = (right - left) / 2 + left;
    var item = array[index];
    var compareResult = item.Name.CompareTo(targetName);
    if (compareResult < 0)
        return BinarySearch(index + 1, right, array, targetName);
    if (compareResult > 0)
        return BinarySearch(left, index - 1, array, targetName);
    return item;
}

Где User это класс со свойством Name

Не смотря на странность задачи, ваша идея решения верная. Нужен метод сравнения массивов, например такой:

int ByteArrayComparer(byte[] a, byte[] b)
{
  //ищем индекс не совпадающего элемента
  int i = 0;
  while(i < a.Length && i < b.Length && a[i] == b[i])
    i++;
  if(a.Length == i || b.Length == i)
  {
    //если все значения меньшего или равного по длине массива
    //совпали с соответствующими по индексам значениями большего 
    //или равного по длине массива
    return a.Length - b.Length;
  }  
  else
  {
    return a[i] - b[i];
  }
}

Результат:

• больше нуля - массив a > массива b
• меньше нуля - массив a < массива b
• ноль - массивы равны

Дальше реализуете двоичный поиск как для обычного массива чисел, только вместо оператора сравнения используете этот метод и проверяете результат.

Есть и другие пути:

• Перед поиском преобразовать исходный массив в string[] или List<string> и работать со строками. Минус - удвоенный объем памяти (или утроенный, если исходные данные в одно-байтовой кодировке). Плюс - более очевидная реализация, т.к. строки поддерживают сравнение и можно использовать обычные операторы сравнения.

• Перед сравнением конвертировать объект из исходного массива в string и, опять же сравнение строк, для которых все уже есть, вместо сравнения массивов. Минус - постоянная генерация новых строк в процессе поиска, но расход памяти существенно меньше чем в предыдущем варианте. Плюс - аналогично предыдущему варианту.

• Самым правильным путем было бы читать данные сразу в массив или даже HashSet строк, и поиск будет работать почти мгновенно "из коробки", но судя по вашему комментарию:

  Я все понимаю, но вот так поставлена задача. База уже в памяти и я работаю с тем, что мне дают. Грузить в память еще одну базу в объектах мне не дадут. – Oleg

  этот вариант вам не подходит.

Делать свою реализацию поиска объекта в массиве - дурной тон. Мы работаем на виртуальной машине и для взаимодействия с объектами нужно использовать именно её средства.

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

Учитывайте, что применять работу с множеством байт нужно только в самых крайних случаях, так как это не даст быстро получить доступ к данных в другой информационной системе, использующей иной язык программирования. Помимо этого, тот же бинарный сериализатор из стандартной библиотеки .Net в процессе работы требует одно пространство имен в месте сохранения объекта в массив байт и его последующего разбора. Это очень мешает при работе с файлом из нескольких программ.

Для поиска нужного объекта рекомендую использовать LINQ запрос. В результате поиск объекта будет реализован в одну строчку! У подобных запросов два варианта написания: SQL-подобный синтаксис или с вызовом методов перечислений, добавленных через расширение. Лично мне больше нравится последний. Кроме того, эти запросы можно легко через Entity Framework подключить к базе данных, а она-то точно найдет объект быстрее.