# Binary Search
#
# Дан отсортированный по возрастанию массив целых чисел nums
# и целое число target. Напиши функцию search(nums, target),
# которая возвращает индекс target в nums, либо -1, если target отсутствует.
#
# Требование: сложность O(log n).
#
# Примеры:
#   search([-1, 0, 3, 5, 9, 12], 9)  →  4
#   search([-1, 0, 3, 5, 9, 12], 2)  →  -1
#
# Ограничения:
#   1 <= nums.length <= 10^4
#   -10^4 < nums[i] < 10^4
#   все элементы nums уникальны
#   nums отсортирован по возрастанию

def search(nums, target)
  left = 0
  right = nums.size - 1

  loop do
    break if right < left
    break if left < 0
    break if right < 0

    middle = (right + left) / 2

    current = nums[middle]

    if current == target
      return middle
    elsif current > target
      right = middle - 1
    else
      left = middle + 1
    end
  end

  -1
end