import java.util.ArrayList; import java.util.Random; /** * Using recursion over arrays * Soemtimes this is a good idea. Usually it involves private recursive functions * to hold the array index. * * @author gtowell * Created: August 11, 2021 */ public class RArray { /** * Make an array with increasing elements but the gaps are random * @param size the size of the array to make * @param maxgap the max space between successive items int he array * @return the array */ public ArrayList makeIncrArray(int size, int maxgap) { return makeIncrArrayUtil(size, maxgap, 0, new Random()); } /** * The private recursive fun that actually does the work * @param arr the array to be filled * @param maxgap the max space between items * @param loc the location of the item being worked (the loop index) * @param r a random number generator * @return the resulting array */ private ArrayList makeIncrArrayUtil(int size, int maxgap, int loc, Random r) { if (loc >= size) return new ArrayList(); ArrayList ai = makeIncrArrayUtil(size, maxgap, loc + 1, r); if (ai.size()>0) ai.add(ai.get(ai.size() - 1) + r.nextInt(maxgap)+1); else ai.add(r.nextInt(maxgap)); return ai; } /** * Find a number in an array of numbers * @param arr the array * @param num the number ot be found * @return the location in the array, or -1 if the number is not i the array */ public int find(ArrayList arr, int num, boolean useA) { if (useA) return findUtil(arr, num, 0); return findUtilB(arr, num, 0, arr.size()-1); } /** * Find be looking at each item. The array may be in any order * @param arr the array to be searched * @param num the number to be found * @param loc the location to consider next * @return the location of num in arr, or -1 if not in arr */ private int findUtil(ArrayList arr, int num, int loc) { if (loc >= arr.size()) return -1; if (arr.get(loc) == num) return loc; return findUtil(arr, num, loc + 1); } /** * An alternate version of finding number in an array * This version requires that the array be sorted * @param arr the arraylist - it must be sorted * @param num the number to be found * @param minPos the lowest position that the item to be found could be at * @param maxPos the highest possible location * @return the location, or -1 if not found */ private int findUtilB(ArrayList arr, int num, int minPos, int maxPos) { if (minPos > maxPos) return -1; int loc = (minPos + maxPos) / 2; if (arr.get(loc) == num) return loc; if (num > arr.get(loc)) return findUtilB(arr, num, loc + 1, maxPos); else return findUtilB(arr, num, minPos, loc - 1); } public static void main(String[] args) { RArray rar = new RArray(); ArrayList rrr = rar.makeIncrArray(200, 2); System.out.println(rrr); System.out.println("The location of " + rrr.get(16) + " is " + rar.find(rrr, rrr.get(16), true)); System.out.println("The location of " + 103 + " is " + rar.find(rrr, 103, true)); System.out.println("The location of " + 103 + " is " + rar.find(rrr, 103, false)); } }