搜索插入位置

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

执行用时 :80 ms, 在所有 Python3 提交中击败了20.28% 的用户
内存消耗 :14.4 MB, 在所有 Python3 提交中击败了5.47%的用户

    class Solution:
        def searchInsert(self, nums: List[int], target: int) -> int:
            if target in nums:
                return nums.index(target)
            else:
                if (target<nums[0]):
                    return 0
                elif (target>nums[len(nums)-1]):
                    nums.append(target)
                    return len(nums)-1
                else:
                    for i in range (0,len(nums)):
                        if nums[i]<target and nums[i+1]>target:
                            nums.insert(i+1, target)
                            return i+1

根据题目得知，已知一个数组是一个排序数组且无重复因素，可通过以下两个方面考虑：
第一个：该数组中存在目标值，list.index()如果包含子字符串返回开始的索引值
第二个：该数组不存在目标值
1）目标值比nums[0]小，返回索引值为0
2）目标值比数组最后一个值都大，将其添加到末尾list.append()，返回添加后的数组的长度需减一（返回添加后的数组，最后一个值的索引值）
3）遍历数组中的元素，寻找nums[i]<target and nums[i+1>target],将目标值添加到索引值i+1的位置，返回索引值 i+1

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        while left <=right:
            mid = (right +left) // 2 
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left

用折半查找算法，left为最左边数的索引值，right为最右边的索引值，折半查找只用于按顺序排列的数组。
首先建立一个while循环，当(left<=right)为False时，跳出循环
在while循环中，如果中间值nums[mid]和target相等时,返回mid
如果中间值nums[mid]<target时,返回left在mid的基础上右移一个
如果中间值nums[mid]>target时,返回right在mid的基础上左移一个
（比较特殊，target小于第一个元素取left,target大于最后一个元素取right）
算法题来自：https://leetcode-cn.com/problems/search-insert-position/