Как сделать бинарный поиск еще быстрее?

Question

У меня есть проблема, связанная с бинарным поиском. Задача - найти правильную границу с помощью бинарного поиска. Этот код работает правильно, но проблема в том, что он недостаточно быстр. Как с этим справиться?

 using System;
 using System.Collections.Generic;

 namespace Autocomplete
 {
public class RightBorderTask
{
    public static int GetRightBorderIndex(IReadOnlyList<string> phrases,
                                           string prefix, int left, int right)
    {
        var middle = (right + left) / 2;
        while (left < right)
        {
            middle = (right + left) / 2;
            if (string.Compare(prefix, phrases[middle],
                               StringComparison.OrdinalIgnoreCase) < 0)
                right = middle;
            else left = middle + 1;
        }
        return (string.Compare(prefix, phrases[left - 1],
                               StringComparison.OrdinalIgnoreCase) 
                               >= 0) ? right : -1;
    }
  }
}