Бинарный поиск в Ruby

Учитывая массив предварительно отсортированных значений, как мы можем вернуть индекс для данного значения с помощью Ruby? В реальной жизни в большинстве случаев вы бы использовали преимущества встроенного в Ruby итеративного поиска #index, но сегодня давайте воспользуемся подходом «сделай сам» с алгоритмом бинарного поиска. Мы будем использовать следующий массив случайных чисел в порядке возрастания:

arr = [1, 5, 7, 30, 51, 55, 67, 88, 89, 100, 102]

Мы будем использовать подход «разделяй и властвуй» к проблеме. Первый шаг — установить переменные для пола и потолка массива. Затем мы запускаем цикл while, в котором мы делаем обоснованные предположения с некоторой условной логикой, чтобы отсеять поле подозреваемых. Нашим первым предположением будет расположение индекса в середине нашего массива.

def binary_search(arr, value)
  floor = 0
  ceiling = arr.length - 1
  counter = 0
  
  while floor <= ceiling
    guess = (floor + ceiling)/ 2
  
    # if guess is correct, then great, but if not, then do 
    # stuff with info learned to make the next try more likely to 
    # succeed!
  
  end
end

Хорошо, теперь об этой логике. Мы знаем, что наше первое предположение будет либо равно, либо меньше, либо больше индекса искомого значения, и с помощью оператора if мы можем использовать эту информацию для быстрого отсеивания больших блоков индексов для каждого последующего предположения. . Если наше предположение слишком низкое, все значения индекса, равные или меньшие, чем предположение, также будут слишком низкими, поэтому мы можем безопасно сбросить нашу переменную пола на guess + 1 для следующего хода. Точно так же, если наше предположение слишком велико, все значения индекса, равные или превышающие предположение, также будут слишком высокими, поэтому мы сбрасываем переменную потолка на guess — 1.

def binary_search(arr, value)
  floor = 0
  ceiling = arr.length - 1
  while floor <= ceiling
    guess = (floor + ceiling)/ 2
    if arr[guess] == value
      puts "#{guess} is right!"
      break
    elsif arr[guess] < value
      puts "Too low. Guess higher."
      floor = guess + 1
    else
      puts "Too high. Guess lower."
      ceiling = guess - 1
    end 
  end
end

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

def binary_search(arr, value)
  floor = 0
  ceiling = arr.length - 1
  counter = 0
  winner = nil
  while floor <= ceiling
    counter +=1
    guess = (floor + ceiling)/ 2
    print "Attempt #{counter}: "
    if arr[guess] == value
      winner = guess
      puts "Index ##{guess} is right!"
      break
    elsif arr[guess] < value
      puts "Too low. Guess higher."
      floor = guess + 1
    else
      puts "Too high. Guess lower."
      ceiling = guess - 1
    end
  end
  
  puts "Your number is not in array" unless winner
end

Здесь мы добавляем переменные для счетчика и победителя. Первый увеличивается в нашем цикле while, чтобы показать, сколько ходов он прошел, чтобы получить ответ. Переменная победителя служит для запуска нашего сообщения об ошибке. Таким образом, при использовании с нашим исходным массивом и значением 88 мы получаем следующий вывод:

arr = [1, 5, 7, 30, 51, 55, 67, 88, 89, 100, 102]
binary_search(arr, 88)
# returns:
Attempt 1: Too low. Guess higher.
Attempt 2: Too high. Guess lower.
Attempt 3: Too low. Guess higher.
Attempt 4: Index #7 is right!

И если мы попробуем метод со значением, которого нет в нашем массиве:

arr = [1, 5, 7, 30, 51, 55, 67, 88, 89, 100, 102]
binary_search(arr, 74)
# returns
Attempt 1: Too low. Guess higher.
Attempt 2: Too high. Guess lower.
Attempt 3: Too low. Guess higher.
Attempt 4: Too high. Guess lower.
Your number is not in array

Метод Ruby #index более универсален (во-первых, он может работать с несортированными массивами), но полезно знать, что скрывается под капотом метода binary_sort.