java - 如何用对数时间算法解决这个问题？

Question

我遇到了以下问题:

现在给定一个长度为 n(n 已知)的双倍数数组作为 double sample[n]，并且它按升序排列(所有元素都不同)。请编写一个带有一个参数double num的函数，它返回sample[n]中最接近参数num的元素的索引.如果 num 恰好位于一个区间的中间，则返回小于它的元素的索引。

这是我的 Java 代码:

public int getIndex(double num) {
    if(sample[0] >= num) {return 0;}
    for(int i = 1, i < sample.length; i++) {
        if(sample[i] == num) {return i;}
        else if(sample[i] > num) {
            return (sample[i]-num) < (num-sample[i-1]) ? i : i-1;
        else {continue;}
    }
    return sample.length;
}

显然是线性复杂度。但是，我的老师告诉我存在 O(log n) 的算法。谁能帮我编码？

Answer 1

您的数组已排序，这意味着您可以使用 binary search .我对这个答案没有什么可补充的，也不会为您提供现成的代码，因为这是您的责任。主要思想是检查数组的中间元素，然后确定应朝哪个方向移动:数组的前半部分或后半部分，依此类推。