Разница в алгоритме двоичного поиска

Насколько я знаю, никаких проверенных ошибок не обнаружено. Однако мне интересно, если есть проблема с использованием arr.Length или же arr.Length - 1. Далее, что касается границ, таких как begin <= end with end = mid - 1 или begin

// размер — это длина массива

private static int BinarySearch(int[] arr, int element)
{
    int begin = 0;
    int end = arr.Length;

    for (; begin < end ;)
    {
        int mid = begin + (( - begin + end) / 2);
        if (arr[mid] == element) return mid;
        if (arr[mid] > element)
        {
            // in left
            end = mid;
        }
        else
        {
            begin = mid + 1;
        }
    }
    return -1;
}

// размер равен длине массива — 1

private static int BinarySearch(int[] arr, int element)
{
    int begin = 0;
    int end = arr.Length - 1;

    for (; begin < end ;)
    {
        int mid = begin + (( - begin + end) / 2);
        if (arr[mid] == element) return mid;
        if (arr[mid] > element)
        {
            // in left
            end = mid;
        }
        else
        {
            begin = mid + 1;
        }
    }
    return -1;
}

Насколько я знаю, никаких проверенных ошибок не обнаружено.

Что ж, тогда вы не проверяли все крайние случаи, не так ли?

Учитывая массив int[] arr = new[] { 1, 2, 3, 4, 5 }; Я бы по крайней мере протестировал следующие крайние случаи:

• первый элемент -> 0 == BinarySearch(arr, 1);
• средний элемент -> 2 == BinarySearch(arr, 3);
• последний пункт -> 4 == BinarySearch(arr, 5);
• несуществующий положительный элемент -> -1 == BinarySearch(arr, 6);
• всегда проверять на ноль -> -1 == BinarySearch(arr, 0);
• несуществующий отрицательный элемент -> -1 == BinarySearch(arr, -1);

При этом вторая версия терпит неудачу при проверке последнего элемента.

Я хотел бы подробнее остановиться на некоторых комментариях, касающихся добавления тегов к сообщениям на правильном языке. Как заявляет @Heslacher, у каждого языка есть свои стандарты и соглашения.

В C # именование методов предполагает, что BinarySearch плохое название для вашего метода. Более подходящее имя было бы FindIndex или же FindIndexUsingBinarySearch. Последнее определенно более многословно, но не оставляет сомнений в том, что делает этот метод.

Комментарий // in left не требуется, поскольку он ничего не сообщает разработчику, о чем он или она еще не знает.

Для двоичного поиска требуется отсортированный массив или, точнее, для вашего метода, массив, отсортированный в порядке возрастания. В C # сокращенное имя параметра arr не одобряется. Вместо этого должно быть array или, возможно, даже sortedArray.

Обращаясь к вашим 2 методам и использованию begin, end, а также mid. В обоих методах begin а также mid являются инклюзивными индексами отсортированного массива, но end является исключительным индексом в первой версии, но включающим индексом во второй. Понимание этого дает представление о том, как исправить вторую версию.

Эта оригинальная строка:

int mid = begin + (( - begin + end) / 2);

Для первого способа должно быть:

int mid = begin + ((end - begin) / 2);

А для второго метода, где end включено, должно быть:

int mid = begin + ((end - begin + 1) / 2);

Во втором методе вам также потребуется настроить:

end = mid;

с участием

end = mid - 1;