【LeetCode】35. Search Insert Positionを解いてみた

2445 ワード
Ruby leetcode Ruby テキストリンク

はじめに

コーディングテスト対策としてLeetCodeの35. Search Insert Positionを解いていく。

問題文を和訳

  • 異なる整数のソートされた配列とターゲット値を指定して、
  • ターゲットが見つかった場合はインデックスを返します。
  • 見つからなかった場合は、順番に挿入された場合のインデックスを返します。
  • O(log n) 時間計算量のアルゴリズムを作成する必要があります。
  • Input: nums = [1,3,5,6], target = 5
  • Output: 2

回答

35_SearchInsertPosition.rb
def search_insert(nums, target)
  left = 0
  right = nums.length - 1
  while left <= right
    middle = (left + right) / 2
    if nums[middle] == target
      return middle
    elsif nums[middle] < target
      left = middle + 1
    else
      right = middle - 1
    end
  end
  return left
end

最後に

難易度はEasyでした。