python-3.x - 在排序数组中找到大于 k 的数字的第一次出现

num_to_find = int(input("Enter the number to be found")) a=[2,20,30] def occur1(a,num_to_find): j = i = 0 while j==0: if a[len(a)-1] > num_to_find: if num_to_find < a[i]: j=1 print(i) break else: i = i + 1 else: ret_state = "The entered number is greater than the numbers in the list" return ret_state print(occur1(a,num_to_find))

j由于额外的变量、糟糕的变量名称（通常用作索引，而不是布尔标志）、使用break、嵌套条件和副作用，这段代码很难推理。这也是低效的，因为它需要在最坏的情况下访问列表中的每个元素，并且无法充分利用列表的排序特性。但是，它似乎有效。

您的第一个误解可能print(i)是打印下一个最大元素的索引而不是元素本身。在您的示例调用中occur1([2, 20, 30], 3))， 1 是 20 在数组中的位置。

其次，一旦找到的元素被打印出来，函数None会在它退出循环后返回，并print尽职尽责地打印None. 希望这可以解释您的输出——您可以使用return a[i]代替break来解决您的直接问题并满足您的期望。

话虽如此，Python为此提供了一个内置模块：bisect. 这是一个例子：

from bisect import bisect_right

a = [1, 2, 5, 6, 8, 9, 15]
index_of_next_largest = bisect_right(a, 6)
print(a[index_of_next_largest]) # => 8

如果下一个大于的数字k超出范围，您可以try/ exceptthat 或使用条件来报告您认为合适的失败。该函数利用了列表使用二分搜索算法排序的事实，该算法在每一步都将搜索空间减半。时间复杂度为 O(log(n))，非常快。

如果您确实希望坚持使用类似于您的解决方案的线性算法，您可以将您的逻辑简化为：

def occur1(a, num_to_find):
    for n in a:
        if n > num_to_find:
            return n

# test it...
a = [2, 5, 10]

for i in range(11):
    print(i, " -> ", occur1(a, i))

输出：

0  ->  2
1  ->  2
2  ->  5
3  ->  5
4  ->  5
5  ->  10
6  ->  10
7  ->  10
8  ->  10
9  ->  10
10  ->  None

或者，如果您想要下一个最大数字的索引：

def occur1(a, num_to_find):
    for i, n in enumerate(a):
        if n > num_to_find:
            return i

但我想强调的是，从各个方面来看，二分搜索都远远优于线性搜索。对于 10 亿个元素的列表，二分搜索将进行大约 20 次比较，在线性版本将进行 10 亿次比较的最坏情况下。不使用它的唯一原因是如果不能保证列表是预先排序的，这里不是这种情况。

为了使这更具体，您可以使用此程序（但在实践中使用内置模块）：

import random

def bisect_right(a, target, lo=0, hi=None, cmps=0):
    if hi is None:
        hi = len(a)

    mid = (hi - lo) // 2 + lo
    cmps += 1

    if lo <= hi and mid < len(a):
        if a[mid] < target:
            return bisect_right(a, target, mid + 1, hi, cmps)
        elif a[mid] > target:
            return bisect_right(a, target, lo, mid - 1, cmps)
        else:
            return cmps, mid + 1

    return cmps, mid + 1

def linear_search(a, target, cmps=0):
    for i, n in enumerate(a):
        cmps += 1

        if n > target:
            return cmps, i

    return cmps, i

if __name__ == "__main__":
    random.seed(42)
    trials = 10**3
    list_size = 10**4
    binary_search_cmps = 0
    linear_search_cmps = 0

    for n in range(trials):
        test_list = sorted([random.randint(0, list_size) for _ in range(list_size)])
        test_target = random.randint(0, list_size)
        res = bisect_right(test_list, test_target)[0]
        binary_search_cmps += res
        linear_search_cmps += linear_search(test_list, test_target)[0]

    binary_search_avg = binary_search_cmps / trials
    linear_search_avg = linear_search_cmps / trials
    s = "%s search made %d comparisons across \n%d searches on random lists of %d elements\n(found the element in an average of %d comparisons\nper search)\n"
    print(s % ("binary", binary_search_cmps, trials, list_size, binary_search_avg))
    print(s % ("linear", linear_search_cmps, trials, list_size, linear_search_avg))

输出：

binary search made 12820 comparisons across
1000 searches on random lists of 10000 elements
(found the element in an average of 12 comparisons
per search)

linear search made 5013525 comparisons across
1000 searches on random lists of 10000 elements
(found the element in an average of 5013 comparisons
per search)

添加的元素越多，线性搜索的情况就越糟糕。

python-3.x - 在排序数组中找到大于 k 的数字的第一次出现

问题描述

解决方案

推荐阅读