leetcode的python实现 刷题笔记35：搜索插入位置的暴力解法和优化解法
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5 输出: 2
示例 2:
输入: [1,3,5,6], 2 输出: 1
示例 3:
输入: [1,3,5,6], 7 输出: 4
示例 4:
输入: [1,3,5,6], 0 输出: 0
class Solution:
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if len(nums) == 0:
return None
# 实现查找到的结果，有就返回当前位置
for i in range(0,len(nums)):
if nums[i] == target:
return i
# 实现查找到的结果，没有时应该放到哪里
for i in range(0,len(nums)):
if len(nums) >1:
if nums[i] < target and nums[i+1] >target:
return i+1
elif nums[0]>target:
return 0
elif nums[-1]<target:
return len(nums)
else:
if nums[0]>target:
return 0
else:
return len(nums)
sl = Solution()
print(sl.searchInsert([1,3,5,6], 5))
print(sl.searchInsert([1,3,5,6], 2))
print(sl.searchInsert([1,3,5,6], 7))
print(sl.searchInsert([1,3,5,6], 0))class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
left = 0
right = len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] > target:
right = mid
elif nums[mid] < target:
left = mid + 1
else:
return mid
return left
sl = Solution()
print(sl.searchInsert([1,3,5,6], 5))
print(sl.searchInsert([1,3,5,6], 2))
print(sl.searchInsert([1,3,5,6], 7))
print(sl.searchInsert([1,3,5,6], 0))
总结：
思路：
1.第一种解法：比较暴力，不需要怎么动脑筋，只需要把可能出现的情况一一列举出来即可。
首先判断下进来的数组是否为空数组，如果是，就返回None。
接着遍历整个数组，如果出现相同的数字，就返回该数字的索引。
如果没有的话就进入第二个遍历，如果数组大小为1，直接比较当前数字大小，然后返回相对应的索引即可。如果数组大小大于1，这个时候就要考虑三种情况了，插入前面（返回0），后面（返回数组大小值），还是中间（返回当前索引的下一个索引）。
2.第二种解法：这就稍微死点脑细胞了。二分查找的思想，先找到中间值，然后判断中间值与target的大小来判断target应该放在中间值的左边还是右边，依次类推，直到找到合适的位置。
首先设定一个最左值和最右值，用于中间值。之所以采用的是mid = left + (right - left) // 2，是为了防止溢出。
然后呢使用while循环来比较，
如果中间值等于target，非常好，返回当前中间值得索引；
如果中间值小于target，说明target应该插在中间值的右边，于是就将最左值变成中间值+1，最右值不变，再次找到新的中间值和target进行比较，直到找到合适的位置。
如果中间值大于target，说明target应该插在中间值的左边，于是就将最左值不变，最右值变成中间值，再次找到新的中间值和target进行比较，直到找到合适的位置。
要注意的点：
1.python3中//返回的是整数，/返回的是浮点数。
2.在一般印象中，我们找中间值都是这样找的，mid = (left + right) / 2。但是left与right之和超过了所在类型的表示范围的话,那么mid就不会得到正确的值，也就是我们常常说的溢出。所以为了避免这个问题，记得以后找中间值应该是这样：mid = left + (right - left) / 2
3.当完成一个算法的时候，光是得到答案是不行的，还要考虑下数据量带来的时间复杂度。