【Leetcode】【python】Search Insert Position 搜索插入位置

题目大意

查找目标数字在排序数组的位置,若没有该数字,则返回应该插入他的位置,假设没有重复数字

解题思路

二分查找的变种

代码

left <= right

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int searchInsert(int[] nums, int target) {
int low = 0;
int high = nums.length-1;
int mid = 0;
while (low <= high) {
mid = low + (high - low) * 1/2;
if(nums[mid] == target) {
return mid;
}
if(nums[mid] > target) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
return low; //return low 应该插入的位置
}
}

left < right

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if not nums:
return 0
left = 0
right = len(nums) - 1
while left < right:
print left, right
mid = (left + right) / 2
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
else:
return mid
if nums[left] < target:
return left + 1
else:
return left

总结

关于二分查找的细节,直接看查找的博客