Рандомизированный алгоритм бинарного поиска

Question

Алгоритм, приведенный ниже, представляет собой вариант бинарного поиска, в котором вместо выбора среднего выбирается и сравнивается случайный индекс. Алгоритм асимптотически хуже, но это была просто задача. Алгоритм рассматривает случай, когда элемент со случайным индексом i равен поисковому значению, в этом случае он возвращает true, а второй случай, когда элемент с индексом i больше, чем значение поиска, и в этом случае мы рекурсивно вызываем поиск на входе n i - 1. И если элемент всегда больше или равен поисковому значению, алгоритм работает нормально.

Однако что происходит, когда элемент рандомизированного индекса меньше значения поиска? Интуитивно я думал, что вход н должен увеличиться я + 1 и даже с проверкой, если п становится больше, чем размер массива, я, кажется, получают stackoverflows ..

public static boolean search(int[] keys, int value, int n) { 
    if(n <= 0 || n > keys.length) 
     return false; 
    else { 
     Random random = new Random(); 
     int i  = random.nextInt(n); 

     if(keys[i] == value) 
      return true; 
     else if(keys[i] > value) 
      return search(keys, value, i - 1); 
     else 
      return search(keys, value, i + 1); 
    } 
} 

Answer 1

Ваш код в корне неправильно (я думаю). Согласно тому, что вы говорите (условия в вашей постановке задачи), то это должно быть код:

public static boolean search(int[] keys, int value, int l, int r) 
{ 
    if(l < 0 || r >= keys.length || l>r) return false; 
    else 
    { 
     Random random = new Random(); 
     int i  = l + random.nextInt(r-l); 

     if(keys[i] == value) return true; 
     else if(keys[i] > value) return search(keys, value, l, i - 1); 
     else return search(keys, value, i + 1, r); 
    } 
} 

Answer 2

Смотрите эту часть вашего кода,

else if(keys[i] > value) 
    return search(keys, value, i - 1); //Line1 
else 
    return search(keys, value, i + 1); //Line2 

Вы ищете в той же части массив в обоих случаях.

Line1 ищет value в массиве от 0 до i - 1.
Line2 ищет value в массиве от 0 до i + 1.

Что вы должны сделать это,

Line1 следует искать value в массиве из 0 в i - 1.
Line2 следует искать value в массиве от i + 1 до конца массива.