Двоичный поиск C# реализация

Question

Вот одна реализация я сделал для Binary поиска

public int FindIndexRecursive(int numberToFind, int[] array, int indexMin, int indexMax) 
{ 
    if (indexMin > indexMax) 
    { 
     return -1; 
    } 

    int mid = ((indexMax - indexMin)/2) + indexMin; 

    if (array[mid] < numberToFind) 
    {     
     return FindIndexRecursive(numberToFind, array, mid, indexMax); 
    } 
    else if (numberToFind < array[mid]) 
    { 
     return FindIndexRecursive(numberToFind, array, indexMin, mid); 
    } 
    else 
    { 
     return mid; 
    } 
} 

он прекрасно работает. я задал вопрос https://codereview.stackexchange.com/questions/71815/binary-search-using-recursion-iteration-shifted-array

и я был ответ, что я могу изменить мой середине расчет

from: int mid = ((indexMax - indexMin)/2) + indexMin; 
to: int mid = ((indexMax - indexMin)/2); 

public int FindIndexRecursive2(int numberToFind, int[] array, int indexMin, int indexMax) 
{ 
    if (indexMin > indexMax) 
    { 
     return -1; 
    } 

    int mid = ((indexMax - indexMin)/2); 
    //since the array is sorted 
    if (numberToFind < array[mid]) 
    { 
     return FindIndexRecursive2(numberToFind, array, indexMin, mid-1); 
    } 
    else if (numberToFind > array[mid]) 
    { 
     return FindIndexRecursive2(numberToFind, array, mid+1, indexMax); 
    } 
    else 
    { 
     return mid; 
    } 
} 

Однако теперь я получаю переполнение стека, что я не хватает в моей новой реализации?

Answer 1

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

(indexMax - indexMin)/2 + indexMinравна(indexMax + indexMin)/2

Answer 2

Как вы относитесь к середине, это (low+high)/2. В противном случае вы получите исключение переполнения стека.

Answer 3

Оригинальный int mid = ((indexMax - indexMin)/2) + indexMin; вычисляет расстояние beween indexMax и indexMin половинок его и использует его для индекса исходного массива относительно indexMin.

Новый int mid = ((indexMax - indexMin)/2); неправильно и должен содержать + вместо -: int mid = ((indexMax + indexMin)/2); Это использует тот факт, что среднее из двух значений как раз посередине между ними.

Если взять ручку и написать это и исходное выражение в виде выражений с дробями, вы пришли к выводу, что они равны:

indexMax - indexMin    indexMax - indexMin 2 · indexMin indexMax + indexMin 
------------------- + indexMin = ------------------- + ------------ = ------------------- 
     2        2     2     2