优化索引数组搜索大于数字

Question

我有一个排序的数字数组：

pts = [ 0, 4, 25, 51, 72, 100 ]

给定值T，我需要找到数组中大于T的第一个数字的索引。

if T = 2, then the correct index is 1 for value 4

哑解

我可以用线性搜索来做这件事，但是我想优化一下。

不工作溶液

二进制搜索算法的例子找到了一个精确数的索引。

有建议的技术来解决这种搜索问题吗？谢谢!

Answer 1

查找t的二进制搜索算法，以使list[t] <= T和list[t+1] > T (或t+1大于列表的长度)

Answer 2

二进制搜索算法通常会找到精确的匹配，但是算法很简单，您应该可以很容易地修改它，以找到大于给定数的第一个数。您是否正在寻找解决方案的特定语言？

Answer 3

二进制搜索将适用于此。

通常，一个实现将返回一个负数来告诉您插入点的情况。例如，在Java中，只有-1-n，您就有了自己的位置。