给定一个有序数组和一个目标值，如果数组中有目标值就返回对应索引，如果没有就返回按序插入目标值的下标
假设数组中不存在重复值
Example 1:1：enumerate()方法遍历数组
Input: [1,3,5,6], 5 Output: 2
Example 2:
Input: [1,3,5,6], 2 Output: 1
Example 3:
Input: [1,3,5,6], 7 Output: 4
Example 4:
Input: [1,3,5,6], 0 Output: 0
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
for index, num in enumerate(nums):#将数组转换为枚举类型
if target <= num:
return index
return len(nums)2：折半法，将数组分成两半进行查找比较
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
start = 0#指向折半搜索头
end = len(nums)-1#指向折半搜索尾
while start <= end:#判断条件
mid = (start+end)//2#折半中间
if nums[mid]==target:
return mid
elif nums[mid]>target:#根据对比大小，重新赋值折半头或尾
end = mid-1
else:
start = mid+1
return start上面是 python 实现，下面是 java 实现的版本
public int searchInsert(int[] nums, int target) {
for (int i = 0;
i < nums.length;
i++) {
if (target <= nums[i]) {
return i;
}
}
return nums.length;
}以下是 go 实现版本
func searchInsert(nums []int, target int) int {
for index , elem:= range nums {
if target <= elem {
return index
}
}
return len(nums)
}【Python、java、go实现"搜索插入位置"的几种方法】算法题来自：https://leetcode-cn.com/problems/search-insert-position/description/
推荐阅读
- Python、java、go实现＂strStr()＂的几种方法
- 欧几里德算法证明
- Data|判断四个点是否可以构成矩形（优雅的解法！！！）
- Data|数据结构与算法笔记: 贪心策略之BST&BBST, Hashtable+Dictionary+Map, Priority Queue~Heap, Minium Spanning Tree
- Data|[转载] 线性表的数组实现