LeetCode-Python-35. 挿入位置の検索

ソート配列とターゲット値を指定し、配列内にターゲット値を見つけ、インデックスを返します.ターゲット値が配列に存在しない場合は、順番に挿入される位置を返します.
配列に重複要素がないと仮定できます.
例1:

  : [1,3,5,6], 5
  : 2

例2:

  : [1,3,5,6], 2
  : 1

例3:

  : [1,3,5,6], 7
  : 4

例4:

  : [1,3,5,6], 0
  : 0

 
第一の考え方:
暴力解は、まずtargetを挿入し、それから重くし、listを回し、ソートし、targetのindexを探せばいい.

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        return sorted(list(set(nums + [target]))).index(target)
        

2つ目の考え方:
二分検索

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        lo,hi = 0, len(nums) - 1
        while (lo <= hi):
            mid = lo + (hi - lo) / 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                hi = mid - 1
            else:
                lo = mid + 1
        return lo

3つ目の考え方:
問題の要件は、実際には次のとおりです.
targetが存在する場合は、target要素の下付き文字を探します.配列が順番に並んでいるので、最初の=target要素の下付き文字を見つければいいです.
targetが存在しない場合、targetが配列の末尾に挿入されない場合、最初の>target要素の下付き文字、例えば[1,3,5]が2を挿入した後に[1,2,3,5]になる.
targetが配列の末尾に挿入されるべき場合は、配列の長さを直接返します.

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        for i, num in enumerate(nums):
            if num >= target:
                return i
        return len(nums)