Java Array Gallop Search

ArrayGallopSearch.java

/* 
 * Copyright (c) 2018 Patrick Sharp
 * 
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 * 
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 * 
 * Modified using code from https://github.com/adam-ho/misc/blob/master/searchPerformance/src/main/java/com/search/Gallop.java
 */

public class ArraySearchUtils {

    /*
     * assuming guess is close galloping could take less time than binary search
     * useful for searches that may need to be done as part of a loop where the
     * previous index found is close to the next index in question
     */
    public static double searchWithGuess(double[] a, double key, int guessIndex){
        if(guessIndex < 0){
            return Arrays.binarySearch(a, x);
        }else{
            boolean forward = guessIndex != a.length && a[guessIndex] <= x;
            if(forward) return gallopSearch(matrix[0], guessIndex, a.length, x, true);
            else return gallopSearch(a, 0, guessIndex, x, false);
        }
    }

    /*
     * gallop to or past key value, then binary search remaining interval
     * better than binary search when key index is close to start index 
     *
     * gallop: O(log(n))
     * binary search: O(log(n))
     * together: O(log(n))
     */
    public static int gallopSearch(final double[] arr, final int fromIndex, final int toIndex, final double key, boolean forward){
        int currentIndex = forward ? fromIndex : (toIndex - 1);
        double currentValue = arr[currentIndex];
        if(forward){
            if(key < currentValue) return -fromIndex - 1;
            for(int jump = 1; ; jump *= 2){
                if(currentValue == key) return currentIndex;

                int nextIndex = currentIndex + jump;
                if(toIndex <= nextIndex) return Arrays.binarySearch(arr, currentIndex, toIndex, key);

                double nextValue = arr[nextIndex];
                if(key < nextValue) return Arrays.binarySearch(arr, currentIndex, nextIndex, key);

                currentIndex = nextIndex;
                currentValue = nextValue;
            }
        }else{
            if(currentValue < key) return -toIndex - 1;
            for(int jump = -1; ; jump *= 2){
                if(currentValue == key) return currentIndex;

                int nextIndex = currentIndex + jump;
                if(nextIndex < fromIndex) return Arrays.binarySearch(arr, fromIndex, currentIndex, key);

                double nextValue = arr[nextIndex];
                if(nextValue < key) return Arrays.binarySearch(arr, nextIndex, currentIndex, key);

                currentIndex = nextIndex;
                currentValue = nextValue;
            }
        }
    }
    
}