首页 > 代码库 > 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.搜索插入位置