二分法

    1. # 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 
    2. # 
    3. #  你可以假设数组中无重复元素。 
    4. # 
    5. #  示例 1: 
    6. # 
    7. #  输入: [1,3,5,6], 5
    8. # 输出: 2
    9. #  
    10. # 
    11. #  示例 2: 
    12. # 
    13. #  输入: [1,3,5,6], 2
    14. # 输出: 1
    15. #  
    16. # 
    17. #  示例 3: 
    18. # 
    19. #  输入: [1,3,5,6], 7
    20. # 输出: 4
    21. #  
    22. # 
    23. #  示例 4: 
    24. # 
    25. #  输入: [1,3,5,6], 0
    26. # 输出: 0
    27. #  
    28. #  Related Topics 数组 二分查找 
    29. #  👍 650 👎 0
    32. # leetcode submit region begin(Prohibit modification and deletion)
    33. class Solution(object):
    34.     def searchInsert(self, nums, target):
    35.         """
    36.         :type nums: List[int]
    37.         :type target: int
    38.         :rtype: int
    39.         """
    40.         left, right = 0, len(nums) - 1
    41.         while left <= right:
    42.             mid = (left + right) // 2
    43.             if nums[mid] > target:
    44.                 right = mid - 1
    45.             elif nums[mid] < target:
    46.                 left = mid + 1
    47.             else:
    48.                 return mid
    49.         return left
    52. # leetcode submit region end(Prohibit modification and deletion)
    54. s = Solution()
    55. print(s.searchInsert([1, 3, 5, 6], 0), '== 0')
    56. print(s.searchInsert([1, 3, 5, 6], 7), '== 4')