java - 检查 int 是否位于数组中的两个项目之间

Question

好吧，我正在用 java 开发一个调平系统。我从上一个定义“exp”级别要求的问题中得到了这个:

    int[] levels = new int[100];
    for (int i = 1; i < 100; i++) {
        levels[i] = (int) (levels[i-1] * 1.1);
    }

现在，我的问题是如何确定 exp 级别是否介于数组中的两个不同整数之间，然后返回两个整数中的较低者？我发现了一些接近的东西，但不完全是我正在寻找的here它说的是二分搜索。一旦我找到 exp 落在哪个值之间，我就能够确定用户的级别。或者，如果其他人有更好的想法，请随时提出。请原谅我可能犯的菜鸟错误，我是 Java 新手。预先感谢您的任何答复。

已解决，感谢所有精彩答案。

Answer 1

对于一般的有序数字数组，二分查找是可行的方法，其时间复杂度为 O(log n)。但由于数字之间存在数学关系(每个数字是前一个数字的 1.1 倍)，因此请利用这一事实。您正在寻找最大指数 level 使得

levels[0] * Math.pow(1.1, level) <= exp

求解水平，

level = log{base 1.1}(exp / levels[0])

利用 log_a(b) = ln(b)/ln(a)...

int level = (int) Math.log(exp/levels[0]) / Math.log(1.1);

由于数学关系，你只需要这个计算，而不需要搜索，所以它是 O(1)。

double base = 1;
double factor = 1.1;

for (double score : Arrays.asList(1.0, 1.1, 1.3, 8.6, 9.46))
{
   int level = (int) (Math.log(score / base) / Math.log(factor));
   System.out.println(level);
}

打印

0
1
2
22
23