Common lookups in Java are

  • Linear search
  • Binary search/split search
  • The interpolation to find
  • Fibonacci search/Golden ratio search

It’s all fairly simple, except Fibonacci search

The following ideas and key methods are only given. The source code of the algorithm is put in Git, and you need to take it yourself

leidl97/algorithm-src

Binary search

thought

Must be in order, can be positive or reverse order

Cut it in half each time. If you find it and return, keep looking left and right

If the target value is larger than mid, recurse to the right; otherwise, recurse to the left.

Optimization: You can find duplicate data, and after you find the elements, you can compare them left and right to find all the same elements

Notice that the boundary value problem left must be <= not <

Code implementation

private static void search(int[] arr,int left, int right, int act) { if (left <= right) { int mid = (left + right) / 2; if (arr[mid] > act) { search(arr, left, mid, act); } else if (arr[mid] < act) { search(arr,mid+1, right, act); } else {system.out.println (" find data "); list.add(arr[mid]); int i = mid+1; If (I < arr. Length) {while (arr[I ++] == arr[mid]) {system.out.println (" find data "); list.add(arr[mid]); } } int j = mid-1; If (j) > 0 {while (arr [-] = = arr (mids)) {System. Out. Println (" find the data "); list.add(arr[mid]); }} System. Out. Println (" find data have "+ list. The size () +" "); }} else {system.out.println (" no such data "); }}Copy the code

The interpolation to find

It’s similar to binary search, where you’re dealing with the inefficient parts of binary search, like an array of 1 to 10, where you’re looking for the 1 or 10 on the edge and you’re looking for it a lot

In other words, you change the way you look for mid, the factor goes from 1/2 to the factor down here, and I don’t know how to figure that out, right

So, key is the value that you’re looking for

Replace this part of the binary lookup code

int mid = left + (right – left) * (act – arr[left]) / (arr[right] – arr[left])

Therefore, for the more uniform lookup table, the use of interpolation search faster

If it’s not uniform, it’s not necessarily faster than bisection

Fibonacci search

I would like to call it metaphysical search, just changed a mid point, but also difficult to understand, fast words also do not have an exact explanation, some said that addition and subtraction faster than multiplication and division, I did not actually test, in fact, is to change a MID search position.

This search takes a little bit of time, and essentially changes the location of the middle node mid

Fibonacci search, also known as the golden section search, divides a line segment into two parts, where the ratio of one part to the full length is equal to the ratio of the other part to this part, and the approximation of the first three digits is 0.618.

The median is not derived from the median or interpolation, but is located near the golden section

F = { 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , . . . }

The difficulties in

1. Why is it necessary to split into f(k-1) -1 instead of F (k-1)?

It is necessary to find the golden section point, that is, the mid point, which can be used as a sign of judgment to facilitate the search forward and backward. Of course, it can also be defined separately, but it will be more troublesome to write

Point of time

2. Why is k-1 for forward lookup and k-2 for backward lookup

Point of time

Why are Fibonacci searches more efficient?

Dichotomy uses division, and this is addition and subtraction

Code implementation

Public class FibonacciSearch {public static void main(String[] args) {int[] a = {1,8,10,89,1000,1234}; sort(a,1234); } //{1,1,2,3,5,8,13,21} private static int[] fib() {int[] fib = new int[20]; fib[0] = 1; fib[1] = 1; for (int i = 2; i < fib.length; i++) { fib[i] = fib[i-1] + fib[i-2]; } return fib; } private static int sort(int[] arr, int act) { int low = 0; int high = arr.length - 1; int k = 0; Int mid = 0; Int [] f = fib(); While (high > f[k] -1) {k++; while (high > f[k] -1) {k++; } // the value of f[k] may be larger than the array length, so it needs to be expanded. Int [] temp = array.copyof (arr,f[k]-1); For (int I = arr.length; i < temp.length; i++) { temp[i] = arr[high]; While (low <= high) {mid = low + f[k-1] -1; If (act < temp[mid]) {if (act < temp[mid]) { F[k-2] + F[k-3] + F[k-1] + F[k-1]; } else if(act > temp[mid]){low = mid + 1; [k-2] = f[k-3] = f[k-3]; } else {if (mid < high) {system.out.println (" find element, subscript: "+mid); return 0; } else {system.out.println (" find element, subscript: "+high); return 0; }} system.out.println (" element not found "); return -1; }}Copy the code