LeetCode|【LeetCode 35】Search Insert Position(Python) LeetCode|python

【LeetCode|【LeetCode 35】Search Insert Position(Python)】Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
题目分析：
给定一个目标和一个有序序列，如果目标在序列中，则返回其索引，否则给出当插入目标且不改变序列性质时插入的位置（索引）。
示例1:
Input: [1,3,5,6], 5
Output: 2
示例 2:
Input: [1,3,5,6], 2
Output: 1
示例 3:
Input: [1,3,5,6], 7
Output: 4
方法一：

思路：用数据结构中的二分法查找，找到就很简单直接返回；没找到，判断目标和nums[mid]的关系，返回索引。
简单回顾一下二分法：一组有序排列的数组，一个目标，和本题一样。第一步—–统计数组内元素个数，找到中点所在位置，返回索引。第二步—-判断目标与中点的大小关系：
1.相等：直接返回中点的索引。
2.大于（目标值大于中点值）：把中点值作为起点，重复第一步。
3.小于（目标值小于中点值）：把中点值作为终点，重复第一步。
优点：时间复杂度减小超过一半。具体是多少不会算。
代码：

class Solution: def searchInsert(self, nums, target): """ :type nums: List[int] :type target: int :rtype: int """ right=len(nums)-1 left=0 while lefttarget: right=mid-1 else: left=mid+1 if target>nums[left]: return left+1 else: return left