优化搜索-任何人都可以帮助计算该算法的复杂性

当我查看二进制搜索算法时。我有一种感觉，可以通过不总是查看中间点来优化搜索点。例如，如果我们在字典中查找单词而不查看菜单，我们将不会总是转到中间页进行比较。如果单词以“ A”开头，我们会期望它在开头附近。如果以“ Z”开头，我们一定会在最后尝试页面。

但是，如果阵列的密度急剧变化，则始终使用当前目标阵列的密度会引起一些严重的问题，这将导致算法在某些情况下最终以接近O（n）的复杂度结束。因此，我根据先前的搜索计算了密度，并始终根据较小的除法来计算密度。并始终根据先前的搜索点计算搜索点。这样，它减轻了密度变化的影响。

因此，我编写了这段代码，试图生成优化的搜索。我还没有测试（甚至还没有编译）。但是我想它解释了算法：

public int OptimizedSearch(int a[], int target) {
        return OptimizedSearch(a, target, 0, a.size(), 0, true);
    }

    public int OptimizedSearch(int a[], int target, int start, int end, double density, boolean fromStart) {
        // Since density is different from the density in current target array, the search point calculated from density will
        // always start from last search point. fromStart records whether the last search point happens at start or end of
        // current array
        if (0 == density) { //Initial density
            density = (a[end] - a[start]) / (end - start);
        }

        int searchPoint;    
        if (fromStart) {
            searchPoint = start + ((target - a[start]) / density).intValue();
        }
        else {
            searchPoint = end - ((a[end] - target) / density).intValue();
        }

        if (a[searchPoint] == target) {
            return searchPoint;
        }
        else if (target < a[searchPoint]) {
            double currentDensity;
            if (end - searchPoint > searchPoint - start) {
                currentDensity = (a[searchPoint] - a[start]) / (searchPoint - start);
            }
            else {
                currentDensity = (a[end] - a[searchPoint]) / (end - searchPoint); 
            } //Density is always calculated from the smaller part since it will be more accurate. 
            return OptimizedSearch(a, target, start, searchPoint - 1, currentDensity, false);
        }
        else {
            double currentDensity;
            if (end - searchPoint > searchPoint - start) {
                currentDensity = (a[searchPoint] - a[start]) / (searchPoint - start);
            }
            else {
                currentDensity = (a[end] - a[searchPoint]) / (end - searchPoint); 
            } //Density is always calculated from the smaller part since it will be more accurate. 
            return OptimizedSearch(a, target, searchPoint + 1, end, currentDensity, true);
        }
    }

但是我真的很难计算复杂度。我觉得它应该低于log（N），但我无法证明这一点。有人可以帮忙吗？