Leetcode 35 Search insert Position

Question

Given a sorted array 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.

 

Solution

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
       return 

 

1일1깡 방법

if target in nums:
	return nums.index(target)
else:
    nums.append(target)
    nums.sort()

return nums.index(target)

 

Binary Search 

low = 0
high = len(nums) - 1
while low <= high:
	mid = (low + high) // 2
if target <= nums[mid]:
	high = mid - 1
else:
	low = mid + 1
   
return low

bisect [link]

return bisect.bisect_left(nums, target)

time complexity, space complexity 모두 bisect가 압도한다...