sharpTrick · April 19, 2018 00:16 · Apr 19, 2018 · Apr 9, 2018 · Apr 3, 2018 · Apr 3, 2018
diff --git a/ArrayGallopSearch.java b/ArrayGallopSearch.java
@@ -54,7 +54,7 @@ public static int gallopSearch(final double[] arr, final int fromIndex, final in
         if(forward){
             if(key < currentValue) return -fromIndex - 1;
             for(int jump = 1; ; jump *= 2){
-                if(currentValue == key) return fromIndex;
+                if(currentValue == key) return currentIndex;
 
                 int nextIndex = currentIndex + jump;
                 if(toIndex <= nextIndex) return Arrays.binarySearch(arr, currentIndex, toIndex, key);
@@ -68,7 +68,7 @@ public static int gallopSearch(final double[] arr, final int fromIndex, final in
         }else{
             if(currentValue < key) return -toIndex - 1;
             for(int jump = -1; ; jump *= 2){
-                if(currentValue == key) return toIndex;
+                if(currentValue == key) return currentIndex;
 
                 int nextIndex = currentIndex + jump;
                 if(nextIndex < fromIndex) return Arrays.binarySearch(arr, fromIndex, currentIndex, key);

diff --git a/ArrayGallopSearch.java b/ArrayGallopSearch.java
@@ -54,7 +54,7 @@ public static int gallopSearch(final double[] arr, final int fromIndex, final in
         if(forward){
             if(key < currentValue) return -fromIndex - 1;
             for(int jump = 1; ; jump *= 2){
-                if(currentValue == key) return toIndex;
+                if(currentValue == key) return fromIndex;
 
                 int nextIndex = currentIndex + jump;
                 if(toIndex <= nextIndex) return Arrays.binarySearch(arr, currentIndex, toIndex, key);

diff --git a/ArraySearchUtils.java → ArrayGallopSearch.java b/ArraySearchUtils.java → ArrayGallopSearch.java
diff --git a/ArraySearchUtils.java b/ArraySearchUtils.java
@@ -0,0 +1,85 @@
+/* 
+ * 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 toIndex;
+
+                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 toIndex;
+
+                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;
+            }
+        }
+    }
+
+}