题目描述

给定一个target和有序序列，如果target在序列中，则返回其索引，否则给出当插入target且不改变序列性质时插入的位置（索引）。

我的解法——遍历数组

遍历一遍数组
注意边界
n的复杂度。
结果：beat 37.26%

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        now = 0
        length = len(nums)
        if(nums[0] > target):
            return 0
        if(nums[length - 1] < target):
            return length
        for i in range(length):
            if(nums[i] <= target):
                now = i
                
        if(nums[now] < target):
            return now + 1
        else:
            return now

简便解法——二分查找

**最好的方法！！ **
logn复杂度
beat 36.87%

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        l = 0
        r = len(nums) - 1
        while(l < r):
            mid = l + (r - l)/2
            if(nums[mid] == target):
                return mid
            elif(nums[mid] > target):
                r = mid - 1
            else:
                l = mid + 1
        if(nums[l] < target):
            return l + 1
        return l

参考答案

https://leetcode.com/problems/remove-element/solution/