GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — Java/Searches/TernarySearch.java at master · feiteng/Java Expand file tree/ Copy pathTernarySearch.javaMore file actions 99 lines (80 loc) · 3.35 KB / Copy pathTernarySearch.javaFile metadata and controls99 lines (80 loc) · 3.35 KB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 package Searches; import java.util.Arrays; import java.util.Random; import java.util.stream.Stream; import static java.lang.String.format; /** * A ternary search algorithm is a technique in computer science for finding the minimum or maximum of a unimodal function * The algorithm determines either that the minimum or maximum cannot be in the first third of the domain * or that it cannot be in the last third of the domain, then repeats on the remaining third. * <p> * Worst-case performance Θ(log3(N)) * Best-case performance O(1) * Average performance Θ(log3(N)) * Worst-case space complexity O(1) * * @author Podshivalov Nikita (https://github.com/nikitap492) * @see SearchAlgorithm * @see IterativeBinarySearch */ public class TernarySearch implements SearchAlgorithm { /** * @param arr The **Sorted** array in which we will search the element. * @param value The value that we want to search for. * @return The index of the element if found. * Else returns -1. */ @Override public <T extends Comparable<T>> int find(T[] arr, T value) { return ternarySearch(arr, value, 0, arr.length - 1); } /** * @param arr The **Sorted** array in which we will search the element. * @param key The value that we want to search for. * @param start The starting index from which we will start Searching. * @param end The ending index till which we will Search. * @return Returns the index of the Element if found. * Else returns -1. */ private <T extends Comparable<T>> int ternarySearch(T[] arr, T key, int start, int end) { if (start > end) { return -1; } /* First boundary: add 1/3 of length to start */ int mid1 = start + (end - start) / 3; /* Second boundary: add 2/3 of length to start */ int mid2 = start + 2 * (end - start) / 3; if (key.compareTo(arr[mid1]) == 0) { return mid1; } else if (key.compareTo(arr[mid2]) == 0) { return mid2; } /* Search the first (1/3) rd part of the array.*/ else if (key.compareTo(arr[mid1]) < 0) { return ternarySearch(arr, key, start, --mid1); } /* Search 3rd (1/3)rd part of the array */ else if (key.compareTo(arr[mid2]) > 0) { return ternarySearch(arr, key, ++mid2, end); } /* Search middle (1/3)rd part of the array */ else { return ternarySearch(arr, key, mid1, mid2); } } public static void main(String[] args) { //just generate data Random r = new Random(); int size = 100; int maxElement = 100000; Integer[] integers = Stream.generate(() -> r.nextInt(maxElement)).limit(size).sorted().toArray(Integer[]::new); //the element that should be found Integer shouldBeFound = integers[r.nextInt(size - 1)]; TernarySearch search = new TernarySearch(); int atIndex = search.find(integers, shouldBeFound); System.out.println(format("Should be found: %d. Found %d at index %d. An array length %d" , shouldBeFound, integers[atIndex], atIndex, size)); int toCheck = Arrays.binarySearch(integers, shouldBeFound); System.out.println(format("Found by system method at an index: %d. Is equal: %b", toCheck, toCheck == atIndex)); } } |
| You are visitor 01402520 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |