Writing in the front

  • Full text data structure

Search algorithm

  • Sequential (linear) lookup
  • Binary search/split search
  • The interpolation to find
  • Fibonacci (Golden ratio) search

In order to find

Public static int seqSearch(int[] arr, int val) {static int seqSearch(int[] arr, int val) { i < arr.length; i++) { if (val == arr[i]) { return i; } } return -1; }Copy the code

Binary search

  • For ordered arrays
Public static int binarySearch(int[] arr, int left, int right, int findVal) { FindVal < midVal, right=left, left>right, left>right, left>right, left>right, left>right, left>right Will directly out of the if (left > right | | findVal < arr [0] | | findVal > arr [arr. Length - 1]) {return - 1; } int mid = (left + right) / 2; int midVal = arr[mid]; if (findVal > midVal) { return binarySearch(arr, mid + 1, right, findVal); } else if (findVal < midVal) { return binarySearch(arr, left, mid - 1, findVal); } else { return mid; }}Copy the code

We have the same number in the array

  • Do not immediately return when you find the mid value, keep scanning left and right to satisfyarr[temp] == findValTo find out all
public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal) { if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) { return new ArrayList<>(); } int mid = (left + right) / 2; int midVal = arr[mid]; if (findVal > midVal) { return binarySearch2(arr, mid + 1, right, findVal); } else if (findVal < midVal) { return binarySearch2(arr, left, mid - 1, findVal); } else { //mid == findVal List<Integer> resIndexlist = new ArrayList<>(); Int temp = mid - 1; while (temp > 0 && arr[temp] == findVal) { resIndexlist.add(temp); temp -= 1; } resIndexlist.add(mid); Temp = mid + 1; while (temp < arr.length && arr[temp] == findVal) { resIndexlist.add(temp); temp += 1; } return resIndexlist; }}Copy the code

The interpolation to find

  • Optimized binary search, suitable for uniform distribution, close to a single function, if not close, not necessarily better than binary search, maybe need to find the value and the ideal value, the gap is larger
  • Adaptive MID, adjust the formula of midint mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left])And approaches the value we’re looking for
  • It’s essentially, in theLeft and rightDraw a line betweenOne dimensional equation.The X-axis is the value and the Y-axis is the index. We assume that thearr[0]witharr[arr.length - 1]Join, then all the values on this line are the ideal distribution of indexes and values, then(right - left) / (arr[right] - arr[left])It’s the slope. Pass(findVal - arr[left])In an ideal world,findValOn this function, we can find the exactmidValue, but in practice, you can also find the surrounding mid value
  • Formula transformation,(mid - left) / (right - left) = (findVal - arr[left]) / (arr[right] - arr[left]) -> (mid - left) / (findVal - arr[left]) = (right - left) / (arr[right] - arr[left])Theta is theta in coordinates(findVal, mid),arr[left], leftwitharr[right], rightThree points
public static int insertSearch(int[] arr, int left, int right, int findVal) { if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) { return -1; } int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]); int midVal = arr[mid]; If (findVal > midVal) {return insertSearch(arr, mid + 1, right, findVal); } else if (findVal < midVal) {// return insertSearch(arr, left, mid-1, findVal); } else { return mid; }}Copy the code

Fibonacci search

  • Golden section search algorithm
  • The Fibonacci sequence, where the ratio of two adjacent numbers is infinitely close to 0.618
  • Modify mid to split the length of a sequence table intoTwo lengths in accordance with the golden ratio, assuming the original table lengthF[k]According to the Fibonacci sequenceF[k]=F[k-1]+F[k-2], so that is to say, divide the table into growth degreesF[k-1]andF[k-2]The two parts of, get the subscript(F[k]-1)=(F[k-1]-1)+(F[k-2]-1)+1So the subscript of mid ismid=low+F[k-1]-1.Low is the initial offset
  • If the length of the table n is differentF[k], then increase the table length to meet the requirements
public static int maxSize = 20; Public static int[] fib() {int[] f = new int[maxSize]; f[0] = 0; f[1] = 1; for (int i = 2; i < maxSize ; i++) { f[i] = f[i - 1] + f[i - 2]; } return f; }Copy the code
  • Fibonacci search
Public static int fibSearch(int[] arr, int key){int low = 0; int high = arr.length - 1; int k = 0; Int mid = 0; Int f[] = fib(); // Get Fibonacci sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34... High =6 arr. Length =7, f[6] = 8, arr. Length =6 But in fact f [k] > arr while (arr. Length > f [k] | | k < 2) {k++; } // If f[k] > arr, construct a new array whose length is the value of the array, and fill the extra part with 0. Int [] temp = array.copyof (arr, f[k]); Temp for (int I = high + 1; i < temp.length; i++) { temp[i] = arr[high]; } mid = low + f[k-1] -1 mid = low + f[k-1] -1 mid = low + f[k-1] -1; If (key < temp[mid] && k >= 0) {if (key < temp[mid] && k >= 0); / / in front of f [k - 1) elements, need to continue to split f = f (k - 1] [2] k + f [k - 3] / /, for example, the number of array elements of 8, mid to subscript 4, low to mid with five elements ` f [k - 1] ` / / at this point, the length of the forward lookup, divided again to the five elements, Mid =f[k-1-1]-1 + low; k --; } else if (key > temp[mid]) {low = mid; / / back length is ` f [k - 2] `, on the back of the length of segmentation / / mid = f] [k - 2-1-1 + low k = 2; } else { if (mid <= high) { return mid; } else {// If mid>high, we are looking for a later element, return high; } } } return -1; }Copy the code