创建二分查找函数以查找插入元素的位置

Question

任务：写一个名为 binary_search 的函数，这个函数的时间复杂度是 O(log n)，目的是找到一个位置来插入一个元素，使得：

binary_search(42, (-5, 1, 3, 5, 7, 10))

结果是 6。

请帮我解决这个问题。我该怎么开始呢？

Answer 1

这是一个二分查找的变种问题，意思是我们要找的是在一个序列中，最大的那个比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

Answer 2

这里有一些可能对你有帮助的内容：这个解决方案的运行时间是 O(log(n))，这和二分查找的效率差不多。你可以查看一下这个关于二分查找的维基百科页面。

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));