[LeetCode] Search Insert Position


📃 問題の説明


Search Insert Position


[質問元:LeetCode]

👨‍💻 解決策


指定した数がリストにある場合は、インデックスが返されます.
ない場合は、昇順ソート基準、挿入する必要がある正しいインデックスを検索して返すことができます.
最初は単純に考えて解いただけで、
バイナリ検索を利用すると、時間の複雑さをさらに減らすことができるようです.
だからバイナリ検索で再開しました.
面白いですね.

バイナリナビゲーション


👨‍💻 ソースコード

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:
            middle = (left + right) >> 1
            if nums[middle] == target:
                return middle
            if target < nums[middle]:
                right = middle - 1
            else:
                left = middle + 1
        return left