diff options
Diffstat (limited to 'src/algorithms')
| -rw-r--r-- | src/algorithms/searching/BinarySearch.java | 231 |
1 files changed, 231 insertions, 0 deletions
diff --git a/src/algorithms/searching/BinarySearch.java b/src/algorithms/searching/BinarySearch.java new file mode 100644 index 0000000..150cca9 --- /dev/null +++ b/src/algorithms/searching/BinarySearch.java @@ -0,0 +1,231 @@ +/** + * Copyright © 2014 Mattias Andrée (maandree@member.fsf.org) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Affero General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +package algorithms.searching; + +import java.util.*; + + +/** + * Binary search class. Binary search runs in logarithmic time, constant memory, + * and requires the list to be sorted. Binary search often out preforms linear + * search, interpolation sort however often out preforms binary search for lists + * with smooth distribution. Identity search is not possible, only equality + * search. Null elements are not allowed, unless the specified compator allows it. + */ +public class BinarySearch +{ + /** + * All elements in the array is the searched for item + */ + public static final int EVERY_ELEMENT = -1; + + /** + * Item was not on the edges, but may be inside + * Values lower than this value indicate that the value does + * not exist. + */ + public static final int MAYBE = -2; + + /** + * The item's value is smaller than the smallest in the array. + * This value and lower values indicate that the value does + * not exist. + */ + public static final int TOO_SMALL = -3; + + /** + * The item's value is larger than the largest in the array + */ + public static final int TOO_LARGE = -4; + + + + /** + * List sort order + */ + public static enum SortOrder + { + /** + * Bigger index, bigger value + */ + ASCENDING, + + /** + * Bigger index, smaller value + */ + DESCENDING, + + } + + /** + * List sort order + */ + public static enum SearchMode + { + /** + * Look for the index of the easiest to find occurence + */ + FIND_ANY, + + /** + * Look for the index of the first occurence + */ + FIND_FIRST, + + /** + * Look for the index of the last occurence + */ + FIND_LAST, + + /** + * Look for both the index of the fist occurence and of the last occurence.<br> + * The returned value will be {@code (LAST << 32) | FIRST}. + */ + FIND_FIST_AND_LAST, + + } + + + +£>for T in boolean char byte short int long float double T T++; do . src/comparable + /** + * Gets whether an item may be contained by a list + * + * @param item The item for which to search + * @param array The list in which to search + * @param order The list's element order + * @return {@link #MAYBE}, {@link #TOO_SMALL}, {@link #TOO_LARGE}, {@link #EVERY_ELEMENT} + * or the index of a(!) found item [first or last position] + */ + public static £(fun "int" contains "${T} item, ${Tarray} array, SortOrder order") + { + int low = £(cmp "array[0]" "item"); + + if (order == SortOrder.ASCENDING) + { + if (low > 0) + return TOO_SMALL; + + int high = £(cmp "array[1]" "item"); + + if (low == 0) + return high == 0 ? EVERY_ELEMENT : 0; + + return high == 0 ? array.length - 1 : high < 0 ? TOO_LARGE : MAYBE; + } + + { + if (low < 0) + return TOO_SMALL; + + int n = array.length - 1; + int high = £(cmp "array[n]" "item"); + + if (low == 0) + return high == 0 ? EVERY_ELEMENT : 0; + + return high == 0 ? n : high > 0 ? TOO_LARGE : MAYBE; + } + } + + + /** + * Finds the first, last or any occurance of an item in a list + * + * @param item The item for which to search + * @param array The list in which to search + * @param order The list's element order + * @param mode The search mode + * @return The index of the found item, if not mode does not say otherwise, or, if not + * found, the bitwise negation of the position to which it should be inserted + */ + public static £(fun "long" indexOf "${T} item, ${Tarray} array, SortOrder order, SearchMode mode") + { + £{Telement} x; + + int min = 0, mid, rc = -1; + int max = array.length - 1; + +£>function f +£>{ + if (mode == SearchMode.£{1}) + for (;;) + { + if (item == (x = array[mid = (min + max) >>> 1])) + £{2}; + + if (£(${3} x item)) min = mid + 1; + else max = mid - 1; + + if (min > max) + return £{4}; + } +£>} + +£>function p +£>{ + for (;;) + { + if (item == (x = array[mid = (min + max) >>> 1])) + { + rc = mid; +£>if [ $3 = 0 ]; then + if (easyMin == -1) + { + easyMax = mid - 1; + easyMin = min; + } +£>fi + } + + if (£(${1} x item)) min = mid + 1; + else max = mid - 1; + + if (min > max) + { + if (rc < 0) + return ~((long)min); + £{2} = rc; + break; + } + } + +£>} + +£>function _ +£>{ + { +£>f FIND_ANY 'return (long)mid' "${1}" '~((long)min)' +£>f FIND_FIRST 'rc = mid' "${1}" 'rc < 0 ? ~((long)min) : (long)rc' +£>f FIND_LAST 'rc = mid' "${1}=" 'rc < 0 ? ~((long)min) : (long)rc' + + int easyMin = -1, easyMax = -1, first, last; +£>p "${1}" first 0 + min = easyMin; + max = easyMax; +£>p "${1}=" last 1 + return (((long)last) << 32) | (long)first; + } +£>} + + if (order == SortOrder.ASCENDING) +£>_ 'greater' +£>_ 'less' + } +£>done +} + |