首页 > 代码库 > LintCode Python 简单级题目 60.搜索插入位置
LintCode Python 简单级题目 60.搜索插入位置
题目描述：
给定一个排序数组和一个目标值，如果在数组中找到目标值则返回索引。如果没有，返回到它将会被按顺序插入的位置。
你可以假设在数组中无重复元素。
您在真实的面试中是否遇到过这个题？
Yes
样例
[1,3,5,6]，5 → 2
[1,3,5,6]，2 → 1
[1,3,5,6]， 7 → 4
[1,3,5,6]，0 → 0
挑战
O(log(n)) time
标签
数组 排序数组 二分法
题目分析:
给定一个排序数组和一个目标值，如果在数组中找到目标值则返回索引。如果没有，返回到它将会被按顺序插入的位置。
你可以假设在数组中无重复元素。
参考代码注释即可。
源码：
class Solution:
"""
@param A : a list of integers
@param target : an integer to be inserted
@return : an integer
"""
def searchInsert(self, A, target):
# write your code here
if A is None: return None
if A == []: return 0
n = len(A)
if A[0] >= target: # 最小的数大于target,插入0；相等,也返回0
return 0
# 这里的if分支可省略
# if A[-1] == target: # 最大的数等于target,返回长度n-1
# return n-1
# elif A[-1] < target: # 最大的数小于target,插入末尾,返回长度n
# return n
# 其余情况，反向遍历列表，找到第一个小于等于target的数
for i in range(-1,-n,-1):
if A[i] > target: # 大于target,继续循环
continue
elif A[i] == target: # 等于，返回n+i;因为i是负数,反向循环
return n+i
else:
return n+i+1 # 小于target，在n+i位置之后插入元素，返回n+i+1
LintCode Python 简单级题目 60.搜索插入位置
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。