One , preface

Search is to find a specific information element in a large amount of information , In computer application , Search is a common basic operation , For example, look up the symbol table in the compiler .

This paper briefly introduces binary search , Interpolation search , fibonacci search .

Search algorithm classification :

1, Static search and dynamic search

2, Unordered search and ordered search

Two , Binary search

1, basic thought

Also known as half search , It belongs to ordered search algorithm . Use the given value value First compare with the keyword of the intermediate node , The middle node divides the linear table into two sub tables , If equal , The search is successful ; If not equal , Again according to K The comparison result with the intermediate node keyword determines which sub table to look for next , This is done recursively , Until the end of the lookup, it is found that there is no such node in the table .

2, Complexity analysis

In the worst case , The number of keyword comparisons is log2(n+1), And the expected time complexity O(log2n);

3, Big talk data structure

The precondition of binary search is to store the ordered table in order , For static lookup tables , No change after one sort , Binary search can get good efficiency . But for data sets that need to perform frequent insert or delete operations, the , Maintaining an orderly sort will bring a lot of work , Binary search is not recommended at this time .

4, Code instance
public static List<Integer> binarySearch2(int[] arr, int left, int right, int
findVal){ // When left > right Time , Recurses the entire array , But I didn't find it if (left > right) { return new
ArrayList<Integer>(); } int mid = (left + right) / 2; int midVal = arr[mid]; if
(findVal > midVal) { // towards Right recursion return binarySearch2(arr, mid + 1, right,
findVal); } else if (findVal < midVal) { // Recursion to the left return binarySearch2(arr,
left, mid - 1, findVal); } else { List<Integer> resIndexlist = new
ArrayList<Integer>(); // towards mid Left scan of index value , All will be satisfied 1000, The subscript of the element , Join to collection ArrayList int
temp = mid - 1; while (true){ if(temp < 0 || arr[temp] != findVal){ break; }
resIndexlist.add(temp); temp--; } resIndexlist.add(mid); // towards mid Right scan of index values , All will be satisfied
1000, The subscript of the element , Join to collection ArrayList temp = mid + 1; while (true){ if(temp > arr.length
- 1 || arr[temp] != findVal){ break; } resIndexlist.add(temp); temp++; } return
resIndexlist; } }
Three , Interpolation search

1, basic thought

Based on binary search algorithm , The search point selection is improved to adaptive selection , It can improve the average performance of search algorithm, which is much better than half search .

If the array is unevenly distributed , So interpolation search may not be a suitable choice .

2,mid Calculation of variables

In binary search :

mid=(left+right)/2;

In interpolation search :

mid=left + (right - left)*(findVal - arr[left])/(arr[right]-arr[left]);

This formula is very good !

3, Code instance
public static int insertValueSearch(int[] arr, int left, int right, int
findVal){ if(left>right || findVal<arr[left] || findVal>arr[right]){ return -1;
} int mid = left + (right - left)*(findVal - arr[left])/(arr[right]-arr[left]);
int midVal = arr[mid]; if(findVal>midVal){ return insertValueSearch(arr,mid +
1,right,findVal); }else if(findVal>midVal){ return
insertValueSearch(arr,left,mid - 1,findVal); }else { return mid; } }
4, Comparison of interpolation search algorithm and binary search algorithm

(1) For large amount of data , For arrays with more evenly distributed values , Using interpolation search algorithm , Faster ;

(2) But for arrays with unevenly distributed values , Binary search algorithm is recommended ;

Four , Fibonacci search algorithm

1, basic thought

Fibonacci sequence is also called golden section sequence , Golden section point ,0.618.

{1,1,2,3,5,8,13,21,55}, Did you find the law , Divide the previous value by the next one , Infinite approach 0.618, This sequence is called Fibonacci sequence .

2,mid Calculation of value

Fibonacci search algorithm and binary search almost , But Fibonacci didn't have recursion , It's just another way to find it mid value ,

mid=left + fibonacciArr[f-1] -1;

fibonacciArr: Represents a Fibonacci array ;

f: Represents the fourth order of Fibonacci sequence f Elements ;

fibonacciArr[f] = fibonacciArr[f-1] + fibonacciArr[f-2];

3, code implementation
// Because we're in the back mid=low+F(k-1)-1, You need to use the Fibonacci sequence , So we need to get a Fibonacci sequence first // Non recursive method to get a Fibonacci sequence
public static int[] fibonacci(){ int[] fibonacci = new int[20]; fibonacci[0] =
1; fibonacci[1] = 1; for (int i = 2; i < fibonacci.length - 1; i++) {
fibonacci[i] = fibonacci[i-1] + fibonacci[i-2]; } return fibonacci; }
// Write Fibonacci search algorithm // Write the algorithm in a non recursive way public static int fibonacciSearch(int[] arr,int
findVal){ int left = 0; int right = arr.length - 1; int f = 0;// The subscript representing the Fibonacci partition value
int mid = 0; int[] fibonacci = fibonacci(); // Obtain the subscript of Fibonacci partition value while (right >
fibonacci[f] - 1){ f++; } // because f[f] value May be greater than arr Of
length , So we need to use Arrays class , Construct a new array , And point to temp[] // The insufficient part will be used 0 fill int[] temp =
Arrays.copyOf(arr,fibonacci[f]); // In fact, it needs to be used arr The last number of the array is filled temp // give an example : //temp = {1,8,
10, 89, 1000, 1234, 0, 0} => {1,8, 10, 89, 1000, 1234, 1234, 1234,} for (int i
= right + 1; i < temp.length; i++) { temp[i] = arr[right]; } //
use while To recycle , Find our number findVal while (left <= right) { //fibonacci seek mid Fixed writing mid =
left + fibonacci[f - 1] - 1; if (findVal < temp[mid]) { // We should continue to look in front of the array ( left )
right = mid - 1; // Why f-- // explain //1. All elements = Previous elements + Elements behind //2. fibonacci[f] =
fibonacci[f-1] + fibonacci[f-2] // because In front of you fibonacci[f-1] Elements , So you can continue to split
fibonacci[f-1] = fibonacci[f-2] + fibonacci[f-3] // Namely stay fibonacci[f-1] Search ahead of
f-- // That is, the next cycle mid = fibonacci[f-1-1]-1 f--; } else if (findVal > temp[mid]) { //
We should continue to look after the array ( right ) left = mid + 1; // Why f -=2 // explain //1. All elements = Previous elements + Elements behind
//2. fibonacci[f] = fibonacci[f-1] + fibonacci[f-2] //3. Because we have it in the back f[f-2] So you can continue to split
fibonacci[f-2] = fibonacci[f-3] + fibonacci[f-4] //4. That is, in fibonacci[f-2] Find in front of
f -=2 //5. That is, the next cycle mid = fibonacci[f - 1 - 2] - 1 f -= 2; }else { // find
// It needs to be determined , Which subscript is returned if(mid <= right) { return mid; } else { return right; } } }
return -1; }
4, Comparison between Fibonacci search algorithm and binary search algorithm

Fibonacci's performance is better than binary search , The experimental data show that , Fibonacci search algorithm is faster than binary search algorithm 17%, But there's a reason for that , Fibonacci search algorithm can only add , Subtraction , There is no multiplication .

In this way, the operation is simplified , It's complicated , Just look at the code .

 

Technology
©2019-2020 Toolsou All rights reserved,
TP6 Application examples of verifier and correct verification data Unity Scene loading asynchronously ( Implementation of loading interface ) Gude Haowen serial - You deserve to be an engineer ( Preface ) Bitcoin in ten years ,VDS Opportunity or fraud Huawei certification HCIA-AI artificial intelligence Image explanation of over fitting and under fitting Python Basic knowledge and notes ESP8266/ESP32 System : Optimize system startup time First knowledge python Skills summary use C++ I want to talk to you “ Prototype mode ” ( copy / copy constructor )