Search of linear table

Catalog

1. Sequential table lookup algorithm

Implementation of sequential search

（ Take a sentry ） Sequential search time efficiency analysis

  Features of sequential search

2. Two points search （ See the column for details ：Acwing Basic courses ）

The implementation of binary search

  Performance analysis of binary search —— Decision tree

  Binary search features

3. Search in blocks

Implementation of block search

  Block search performance analysis

Block search feature  

 4. The interpolation to find （ understand ）

5. Fibonacci looks for

---

1. Sequential table lookup algorithm

Implementation of sequential search

 

 

  improvement ： Application &,for Add a semicolon after the loop

improvement ： Put the key words to be checked key Save to header （ sentry ）, Compare one by one from the back to the front , It can eliminate the need to check whether the search is completed at every step of the search process , Speed up

When ST.length large , This improvement can reduce the average time required for a search by almost half

（ Take a sentry ） Sequential search time efficiency analysis

 

 

  Features of sequential search

2. Two points search （ See the column for details ：Acwing Basic courses ）

The implementation of binary search

 

  Normal half search

  Recursive algorithm for binary search

  Performance analysis of binary search —— Decision tree

 

 

  Time complexity O(logn)

  Binary search features

The reason why the linear linked list is invalid is that it cannot be found mid 

3. Search in blocks

Implementation of block search

Conditions ：1. Divide the watch into several pieces , And the table or order , Or block by block ; if i<j, Is the first j The keywords of all records in the block are greater than the first i The largest keyword in the block

           2. establish “ Index table ”（ Each node contains the largest keyword and a pointer to the first node of this block , And ordered by keywords ）

  Block search performance analysis

Block search feature  

 4. The interpolation to find （ understand ）

5. Fibonacci looks for

int Fibonacci_Search(int* a, int n, int key)
{
	int low, high, mid, i, k;
	low = 1;                 // Define the lowest subscript as the record first 
	high = n;                // Define the highest subscript as the record end 
	k = 0;
	while (n > F[k] - 1)     // Calculation n The position of the Fibonacci series 
		k++;
	for (i = n; i < F[k] - 1; i++) // Fill in the dissatisfied figures 
		a[i] = a[n];

	while (low <= high)
	{
		mid = low + F[k - 1] - 1;  // Calculate the subscript of the current partition 
		if (key < a[mid])          // If the search record is smaller than the current delimited record 
		{
			high = mid - 1;        // Adjust the highest subscript to the split subscript mid-1 It's about 
			k = k - 1;             // The Fibonacci sequence is reduced by one place 
		}
		else if (key > a[mid])     // If the search record is larger than the current delimited record 
		{
			low = mid + 1;         // Adjust the lowest subscript to the separated subscript mid+1 It's about 
			k = k - 2;             // Fibonacci sequence subscript minus two digits 
		}
		else
		{
			if (mid <= n)
				return mid;        // If it is equal, it means mid That's where we found it 
			else 
				return n;          // if mid>n, The description is to complete the value , return n
		}
	}
	return 0;
}