leetcodeday35 -搜索插入位置

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

请必须使用时间复杂度为 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

思路 ： 时间复杂度为 O(log n) 的算法 首先想到的是二分查找，递归，每次查找mid值，如果大于mid，在右边寻找，否则在左边寻找。

二分搜索是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

# @lc code=start
#思路：二分查找
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        def binarySearch (arr, l, r, x): 
  
            # 基本判断
            if r >= l: 
  
                mid = int(l + (r - l)/2)

  
            # 元素整好的中间位置
                if arr[mid] == x: 
                    return mid 
          
        # 元素小于中间位置的元素，只需要再比较左边的元素
                elif arr[mid] > x: 
                    return binarySearch(arr, l, mid-1, x) 
  
        # 元素大于中间位置的元素，只需要再比较右边的元素
                else: 
                    return binarySearch(arr, mid+1, r, x) 
  
            else: 
        # 不存在
                return r+1
        return binarySearch(nums,0, len(nums)-1,target )
# @lc code=end