diff options
Diffstat (limited to 'src/algorithms')
| -rw-r--r-- | src/algorithms/searching/MultibinarySearch.java | 54 |
1 files changed, 51 insertions, 3 deletions
diff --git a/src/algorithms/searching/MultibinarySearch.java b/src/algorithms/searching/MultibinarySearch.java index 841a4eb..868b2d6 100644 --- a/src/algorithms/searching/MultibinarySearch.java +++ b/src/algorithms/searching/MultibinarySearch.java @@ -101,6 +101,55 @@ public class MultibinarySearch */ public static Β£(fun "long[][]" indexOf "${T}[] items, ${Tarray} array, SortOrder order, SearchMode mode") { + return indexOf(items, array, order, mode, 0, array.length - 1Β£{Targ_name}); + } + + /** + * Find the indices of multiple items in a list, with time + * complexity π(log n + m) and memory complexity π(log m) + * + * @param items Sorted list of unique items for which to search, the number + * of elements is named βmβ in the complexity analysis + * @param array Sorted list in which to search, the number of elements + * is named βnβ in the complexity analysis + * @param order The lists' element order + * @param mode The search mode + * @param start The index of the first position to search in the array + * @return Two arrays of integer arrays, the 0:th being the indices + * of items, the 1:th being their positions. That is, + * two separate arrays, not and array of pairs. The expected + * position is returned inverted if it was not found, the + * position it whould have upon be inserted, otherwise the + * position is returned as an index if the mode does not + * specify anything else. + */ + public static Β£(fun "long[][]" indexOf "${T}[] items, ${Tarray} array, SortOrder order, SearchMode mode, int start") + { + return indexOf(items, array, order, mode, start, array.length - 1Β£{Targ_name}); + } + + /** + * Find the indices of multiple items in a list, with time + * complexity π(log n + m) and memory complexity π(log m) + * + * @param items Sorted list of unique items for which to search, the number + * of elements is named βmβ in the complexity analysis + * @param array Sorted list in which to search, the number of elements + * is named βnβ in the complexity analysis + * @param order The lists' element order + * @param mode The search mode + * @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 Two arrays of integer arrays, the 0:th being the indices + * of items, the 1:th being their positions. That is, + * two separate arrays, not and array of pairs. The expected + * position is returned inverted if it was not found, the + * position it whould have upon be inserted, otherwise the + * position is returned as an index if the mode does not + * specify anything else. + */ + public static Β£(fun "long[][]" indexOf "${T}[] items, ${Tarray} array, SortOrder order, SearchMode mode, int start, int end") + { if (mode != SearchMode.FIND_ANY) throw new Error("Mode not implemented"); /* TODO */ if (order != SortOrder.ASCENDING) @@ -122,7 +171,6 @@ public class MultibinarySearch if ((m & 0x00000002) != 0) { lb_m += 1; } int[][] minomax = new int[4][lb_m]; - int n = array.length - 1; m = items.length - 1; int rc_i = 0; @@ -131,8 +179,8 @@ public class MultibinarySearch minomax[0][mm_i] = 0; minomax[1][mm_i] = m; - minomax[2][mm_i] = 0; - minomax[3][mm_i++] = n; + minomax[2][mm_i] = start; + minomax[3][mm_i++] = end - 1; while (mm_i-- > 0) { |