- 2020-05-26 14:57
*views 2*- Data structure and algorithm

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

- Java377 articles
- Python197 articles
- Linux110 articles
- MySQL83 articles
- Vue78 articles
- SpringBoot68 articles
- Spring61 articles
- javascript56 articles
- more...

Daily Recommendation

views 4

©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 ）