leetcode 35 python

class Solution:
def searchInsert(self, nums, target):
“”"
:type nums: List[int]
:type target: int
:rtype: int
“”"

    index = 0
    for i in nums:
        if target > i:
            index += 1
        else:
            return index
    return index
1
2
3
4
5
6
7

看其他大佬的，自己写的暴力解法超时，刚开始刷题，加油！

顺便记录一下二分查找法，简单来说就是在有序序列中，想将target与序列中部数据进行比较，若大于则在大的半区重复上述方法，小于同理。
public class Solution {

public int searchInsert(int[] nums, int target) {
    int len = nums.length;
    // 特殊判断
    if (nums[len - 1] < target) {
        return len;
    }

    // 程序走到这里一定有 nums[len - 1] >= target，插入位置在区间 [0..len - 1]
    int left = 0;
    int right = len - 1;
    // 在区间 nums[left..right] 里查找第 1 个大于等于 target 的元素的下标
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target){
            // 下一轮搜索的区间是 [mid + 1..right]
            left = mid + 1;
        } else {
            // 下一轮搜索的区间是 [left..mid]
            right = mid;
        }
    }
    return left;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

}

python实现
class Solution(object):
def searchInsert(self, nums, target):
n = len(nums)
if target > nums[-1]:
return n
left, right = 0, n-1
ans = -1
while left <= right:
mid = (left + right) // 2
if target <= nums[mid]:
right = mid - 1
ans = mid
else:
left = mid + 1
return ans