Optimized search - can anyone help to calculate the complexity of this algorithm

Question

when I looked at the binary search algorithm. I have a feeling that the search point might be optimized by not always looking at the middle point. For example, if we are looking up a word in dictionary without looking at the menu, we will not always turn to the middle page to compare. If the word starts with 'A', we will expect it at near the beginning. If it starts with 'Z', we will definitely try with the pages at the end.

But, always using the density of the current target array will cause some significant issue if the density of the array changes drastically, which will result the algorithm ends up with a near O(n) complexity in some instances. Thus I calculated the density based on previous search, and always calculates density from the smaller divide. And calculates the search point always from previous search point. In that, it mitigates the impact of changing density.

So I wrote this code trying to generate an optimized search. I haven't tested it (not even compiled yet). But I guess it explains the algorithm:

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);
        }
    }

But I really find it hard to calculate the complexity. I have a feeling it should be lower than log(N), but I can't prove it. Can someone help with it?

Answer 1

This an implementation of interpolation search and if the approximation of the distribution of the elements is good enough it has complexity log(log(n)). It is far from trivial to prove that, though.