LeetCode： Search Insert Position

Question

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

Example 1:

Input: nums = [1,3,5,6], target = 5

Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2

Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7

Output: 4

Solution

此題可以參考前一篇 binary search 的文章來解答。 在上一篇，當 nums 集合內搜尋不到目標元素時會回傳 -1，本題則是需要以大小順序回傳合適的位置。

因此我們可以拿 binary search 的程式碼來修改，以 push 方法將目標元素加入 nums 集合中。接著再以 sort! 方法重新排序，最後用 index 方法就可以取得 target 元素所在的位置了。

def search_insert(nums, target)
  min = 0
  max = nums.length - 1
  while min <= max
    mid = (min + max) / 2
    if nums[mid] == target
        return mid
    elsif nums[mid] > target
        max = mid - 1
    else
        min = mid + 1
    end
  end
  nums.push(target)
  nums.sort!
  nums.index(target)
end