#!/usr/bin/env python3
# -*- coding:utf-8 -*-
# author: bigfoolliu


"""
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

 

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4
示例 4:

输入: nums = [1,3,5,6], target = 0
输出: 0
示例 5:

输入: nums = [1], target = 0
输出: 0
 

提示:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为无重复元素的升序排列数组
-104 <= target <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-insert-position
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""


from typing import List
import doctest


class Solution:
    """
    >>> s = Solution()
    >>> s.searchInsert([1, 3, 5, 6], 5)
    2
    >>> s.searchInsert([1, 3, 5, 6], 2)
    1
    >>> s.searchInsert([1, 3, 5, 6], 7)
    4
    >>> s.searchInsert([1, 3, 5, 6], 0)
    0
    >>> s.searchInsert([1], 0)
    0
    >>> 

    """

    def searchInsert(self, nums: List[int], target: int) -> int:
        # # 常规思路
        # for index, item in enumerate(nums):
        #     if item >= target:
        #         return index
        #     if index == len(nums) - 1 and item < target:
        #         return len(nums)

        mid = -1
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            print(left, right, mid)
            if target == nums[mid]:
                return mid
            elif target > nums[mid]:
                left = mid + 1
            else:
                right = mid - 1
        if mid < left:
            return mid + 1
        else:
            return mid


if __name__ == '__main__':
    doctest.testmod()

#!/usr/bin/env python3
# -*- coding:utf-8 -*-
# author: bigfoolliu


"""
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

 

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4
示例 4:

输入: nums = [1,3,5,6], target = 0
输出: 0
示例 5:

输入: nums = [1], target = 0
输出: 0
 

提示:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为无重复元素的升序排列数组
-104 <= target <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-insert-position
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""


from typing import List
import doctest


class Solution:
    """
    >>> s = Solution()
    >>> s.searchInsert([1, 3, 5, 6], 5)
    2
    >>> s.searchInsert([1, 3, 5, 6], 2)
    1
    >>> s.searchInsert([1, 3, 5, 6], 7)
    4
    >>> s.searchInsert([1, 3, 5, 6], 0)
    0
    >>> s.searchInsert([1], 0)
    0
    >>> 

    """

    def searchInsert(self, nums: List[int], target: int) -> int:
        # # 常规思路
        # for index, item in enumerate(nums):
        #     if item >= target:
        #         return index
        #     if index == len(nums) - 1 and item < target:
        #         return len(nums)

        mid = -1
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            print(left, right, mid)
            if target == nums[mid]:
                return mid
            elif target > nums[mid]:
                left = mid + 1
            else:
                right = mid - 1
        if mid < left:
            return mid + 1
        else:
            return mid


if __name__ == '__main__':
    doctest.testmod()

#!/usr/bin/env python3 # -*- coding:utf-8 -*- # author: bigfoolliu 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。  请必须使用时间复杂度为 O(log n) 的算法。     示例 1:  输入: nums = [1,3,5,6], target = 5 输出: 2 示例 2:  输入: nums = [1,3,5,6], target = 2 输出: 1 示例 3:  输入: nums = [1,3,5,6], target = 7 输出: 4 示例 4:  输入: nums = [1,3,5,6], target = 0 输出: 0 示例 5:  输入: nums = [1], target = 0 输出: 0    提示:  1 <= nums.length <= 104 -104 <= nums[i] <= 104 nums 为无重复元素的升序排列数组 -104 <= target <= 104  来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/search-insert-position 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 >>> s = Solution()     >>> s.searchInsert([1, 3, 5, 6], 5)     2     >>> s.searchInsert([1, 3, 5, 6], 2)     1     >>> s.searchInsert([1, 3, 5, 6], 7)     4     >>> s.searchInsert([1, 3, 5, 6], 0)     0     >>> s.searchInsert([1], 0)     0     >>> # # 常规思路 # for index, item in enumerate(nums): #     if item >= target: #         return index #     if index == len(nums) - 1 and item < target: #         return len(nums)