Iterate through the array from left to right. Return the index of the first element that is greater than or equal to the target. If no such element is found, the target should be inserted at the end.
Use binary search to find the correct insertion index in O(log n) time. Maintain left and right pointers and narrow the search window by comparing the middle element to the target. When the loop ends, left is the correct insert position.
""" 0035.1 - Search Insert Position - Solution 1 - Linear Scan """
#####################################################################################
# Imports
#####################################################################################
from typing import List
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def searchInsert(self, nums: List[int], target: int) -> int:
"""Search Insert Position Function"""
for i in range(len(nums)):
if nums[i] >= target:
return i
return len(nums)
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().searchInsert([1, 3, 5, 6], 5)) # 2
print(Solution().searchInsert([1, 3, 5, 6], 2)) # 1
print(Solution().searchInsert([1, 3, 5, 6], 7)) # 4
print(Solution().searchInsert([1, 3, 5, 6], 0)) # 0
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0035.2 - Search Insert Position - Solution 2 - Binary Search """
#####################################################################################
# Imports
#####################################################################################
from typing import List
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def searchInsert(self, nums: List[int], target: int) -> int:
"""Search Insert Position Function"""
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().searchInsert([1, 3, 5, 6], 5)) # 2
print(Solution().searchInsert([1, 3, 5, 6], 2)) # 1
print(Solution().searchInsert([1, 3, 5, 6], 7)) # 4
print(Solution().searchInsert([1, 3, 5, 6], 0)) # 0
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()