问题描述
任务：编写一个具有 O(log n) 时间复杂度的函数 binary_search 来找到插入元素的位置，使得：
binary_search(42, (-5, 1, 3, 5, 7, 10))
给 6。
请帮我解决这个问题。 我如何接近它？
1楼
以下内容可能会有所帮助：此解决方案的运行时间为 O(log(n))。 类似于 Binary Search
def rec(nums, target, lower, upper):
if (lower > upper):
return lower
mid = int((upper + lower) / 2)
if (nums[mid] > target):
return rec(nums,target,lower,mid-1);
elif (nums[mid] < target):
return rec(nums,target,mid+1,upper);
else:
return mid
class Solution:
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
return(rec(nums, target, 0,len(nums)-1));
2楼
这是二分查找的一个变体问题，它与查找序列中小于k（要插入的元素）的最大元素或大于k的最小元素相同。
def binary_search_insert(target, seq):
U = len(seq) - 1
L = 0
result = 0
if target <= seq[0]:
result = 0
elif target >= seq[len(seq) - 1]:
result = len(seq)
else:
while L <= U:
M = (L + U)/2
if seq[M] <= target:
L = M + 1
else:
result = M
U = M -1
return result
#test case
In [34]: seq
Out[34]: [1, 2, 3, 4]
In [35]: k = 2
In [36]: binary_search_insert(k, seq)
Out[36]: 2
In [37]: k = 2.5
In [38]: binary_search_insert(k, seq)
Out[38]: 2
In [39]: k = 3.5
In [40]: binary_search_insert(k, seq)
Out[40]: 3