Будет ли моя реализация бинарного поиска работать правильно?

Question

Я написал код для двоичного поиска массива целых чисел в scala, который показан ниже. Я знаю, что бинарный поиск довольно сложно реализовать. Итак, я хочу знать, будет ли этот код работать правильно. Я пробовал его, тестируя его на тестовом массиве, и он работает. Однако я не уверен, что это будет всегда работать.

ПРИМЕЧАНИЕ: Предположим, что размер массива не превышает половины максимального целочисленного значения.

def binarySearch(arr: Array[Int], starti: Int, endi: Int, x: Int) : Int = 
{ 
    if (starti > endi) 
     return -1 

    val guess = (starti + endi)/2 

    if (arr(guess) == x) 
     return guess 

    if ((guess != 0) && (arr(guess-1) == x)) 
     return guess - 1 

    if ((guess != endi) && (arr(guess+1) == x)) 
     return guess + 1 

    if (arr(guess) > x) 
     return binarySearch(arr, starti, guess-1, x) 
    else 
     return binarySearch(arr, guess+1, endi, x) 
} 

Answer 1

По вашим предположениям это кажется правильным. Тем не менее, я всегда рекомендую писать val guess = starti + (endi - starti)/2 вместо val guess = (starti + endi)/2, так как последний может переполняться в общем случае (но не по вашему предположению).

Кроме того, поиск соседей довольно редко и в вашем случае его просто над головой, так как вы используете return binarySearch(arr, starti, guess-1, x) вместо return binarySearch(arr, starti, guess-2, x) и аналогично для return binarySearch(arr, guess+1, endi, x), не обращая внимания, что вы уже проверили их.

Я бы рекомендовал удалить тесты для соседей guess. Вместо этого вычислите размер интервала (endi - starti) и, если он меньше некоторого порогового значения, линейно просматривайте массив для x (линейные обходы довольно быстрые из-за того, как работают кеши). Если он больше, используйте рекурсивный двоичный поиск. Обратите внимание, что в следующем примере я немного изменил интерфейс: данный интервал поиска не включает endi, чтобы сделать начальный вызов более удобным (binarySearch(arr, 0, arr.length, x)).

def binarySearch(arr: Array[Int], starti: Int, endi: Int, x: Int) : Int = 
{ 
    val threshold = 100 

    val len = endi - starti 
    if (len <= 0) { 
     return -1 
    } 

    // Optional and purely for performance reasons 
    if (len < threshold) { 
     for (i <- starti until endi) { 
      if (arr(i) == x) { 
       return i 
      } 
     } 
    } 


    val guess = starti + len/2 
    if (arr(guess) == x) { 
     return guess 
    } else if (arr(guess) > x) { 
     return binarySearch(arr, starti, guess, x) 
    } else { 
     return binarySearch(arr, guess + 1, endi, x) 
    } 
} 

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