From 0a30c3ab8f4aaab3aca7d43ca889f18e693a5222 Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Tue, 21 Jan 2014 16:39:54 +0100 Subject: partial array support in interpolation search MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- src/algorithms/searching/InterpolationSearch.java | 66 +++++++++++++++++++++-- 1 file changed, 62 insertions(+), 4 deletions(-) diff --git a/src/algorithms/searching/InterpolationSearch.java b/src/algorithms/searching/InterpolationSearch.java index 1e4aaa8..63bfd17 100644 --- a/src/algorithms/searching/InterpolationSearch.java +++ b/src/algorithms/searching/InterpolationSearch.java @@ -41,10 +41,39 @@ public class InterpolationSearch * negation of the position it insert it in is returned if it was not found. */ public static int indexOf(£{T} item, £{T}[] array) + { + return indexOf(item, array, 0, array.length); + } + + /** + * Find the easiest to find occurance of an item in a list + * + * @param item The item to find + * @param array The list in which to search + * @param start The index of the first position to search in the array + * @return The index of the easiest to find occurance of the item. The bitwise + * negation of the position it insert it in is returned if it was not found. + */ + public static int indexOf(£{T} item, £{T}[] array, int start) + { + return indexOf(item, array, start, array.length); + } + + /** + * Find the easiest to find occurance of an item in a list + * + * @param item The item to find + * @param array The list in which to search + * @param start The index of the first position to search in the array + * @param end The index after the last position to search in the array + * @return The index of the easiest to find occurance of the item. The bitwise + * negation of the position it insert it in is returned if it was not found. + */ + public static int indexOf(£{T} item, £{T}[] array, int start, int end) { £{T} low, high, at; - int min = 0, mid; - int max = array.length - 1; + int min = start, mid; + int max = end - 1; for (;;) { @@ -73,10 +102,39 @@ public class InterpolationSearch * negation of the position it insert it in is returned if it was not found. */ public static int indexOf(£{T} item, £{T}[] array) + { + return indexOf(item, array, 0, array.length); + } + + /** + * Find the easiest to find occurance of an item in a list + * + * @param item The item to find + * @param array The list in which to search + * @param start The index of the first position to search in the array + * @return The index of the easiest to find occurance of the item. The bitwise + * negation of the position it insert it in is returned if it was not found. + */ + public static int indexOf(£{T} item, £{T}[] array, int start) + { + return indexOf(item, array, start, array.length); + } + + /** + * Find the easiest to find occurance of an item in a list + * + * @param item The item to find + * @param array The list in which to search + * @param start The index of the first position to search in the array + * @param end The index after the last position to search in the array + * @return The index of the easiest to find occurance of the item. The bitwise + * negation of the position it insert it in is returned if it was not found. + */ + public static int indexOf(£{T} item, £{T}[] array, int start, int end) { £{T} low, high, at; - int min = 0, mid; - int max = array.length - 1; + int min = start, mid; + int max = end - 1; for (;;) { -- cgit v1.2.3-70-g09d2