leetcode/dichotomy/search_insert.py

from typing import List

import pytest


def searchInsert(nums: List[int], target: int):
    lens = len(nums)
    # 普通解法
    # if target in nums:
    #     return nums.index(target)
    # else:
    #     for i in range(lens):
    #         if target <= nums[i]:
    #             nums.insert(i, target)
    #             return i
    # return lens

    # 二分法
    left, right = 0, lens - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return left



# print(searchInsert([1,3,5,6], 5))

@pytest.mark.parametrize(
    "nums, target, expect",
    [
        ([1,3,5,6], 0, 0),
        ([1,3,5,6], 5, 2),
        ([1,3,5,6], 2, 1),
        ([1,3,5,6], 7, 4)
    ]
)
def test_cases(nums, target, expect):
    assert searchInsert(nums, target) == expect