Search Insert Position

https://leetcode.com/problems/search-insert-position/

algorithm の runtime は O(log n) である必要があるため、 binary search で target の数の位置を調べる。

変数 left に 0、 right に len(nums) - 1 を設定する。

(left + right) // 2 で真ん中の値が取得出来るので、 真ん中の位置を mid とする。

nums の mid の値が target なら、mid の index の値を返す。 もし、target の値が mid より大きい場合、 left を mid + 1 にする。 target の値が mid より小さい場合、 right を mid - 1 にする。

[1, 3, 5, 6] で target = 2 の場合、

[1, 3, 5, 6] l m r

targetの2 は nums[mid]より小さいので、 r の位置が、 mid - 1 のため、一番左になる。 [1, 3, 5, 6] l m
r

次のループで mid の位置が(0 + 0) // 2 で 0 になる。 target が nums[mid] より大きいので、 left の位置を +1 して右にずらす。 [1, 3, 5, 6] r l m

left が right の場所を超えたので、 この時点でループを抜け、left を return する。

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

        while left <= right:
            mid = (left + right) // 2

            if target == nums[mid]:
                return mid

            if target > nums[mid]:
                left = mid + 1
            else:
                right = mid - 1
        return left