1 common search concepts

• Lookup refers to determining a data element whose keyword is equal to the given value in the lookup table according to a given value.
• A lookup table is a collection of data elements or records of the same type.
• Keyword is the value of a data item in a data element, also known as key value. The primary keyword can uniquely identify a record, and the secondary keyword can identify multiple data elements or records.
• Static lookup table: a lookup table that only performs lookup operations. Data can be organized using a linear table structure.
• Dynamic lookup table: in the process of lookup, insert data elements that do not exist in the lookup table at the same time, or delete an existing data element from the lookup table. Binary sort trees can be used to organize data.
• Logically, the data structure on which the search is based is a set, and there is no essential relationship between the records in the set. If we want to obtain high search performance, we can change the relationship between data elements and organize the search set into table, tree and other structures during storage.

2 sequential table lookup algorithm

• Is the most basic search technology, which is suitable for the search of small data. Records that are easy to find can be put in front to improve efficiency.
• The time complexity is O(n)

bool sequentialSearch1(const int* a, int n, int key, int& pos)
{
	for(int i = 0; i < n; ++i)
	{
		if(a[i] == key)
		{
			pos = i;
			return true;
		}
	}
	return false;
}

//Optimize the sequence table search algorithm, and set the sentry in a[0]
bool sequentialSearch2(const int* a, int n, int key, int& pos)
{
	int i = n;
	while(a[i] != key)
		--i;
	if(i == 0)
		return false;
	else
	{
		pos = i;
		return true;
	}
}

3 ordered table lookup

3.1 half search

• Also known as binary search, records must be keyword ordered and stored in order. It is suitable for static lookup tables. For data sets that need frequent insertion or deletion operations, maintaining orderly sorting will bring a large workload and is not suitable for use.
• The time complexity is O(logn)

bool binarySearch(const int* a, int n, int key, int& pos)
{
	int low = 0;
	int high = n - 1;
	while(low <= high)
	{
		int mid = (low + high) / 2;
		if(key < a[mid])
			high = mid - 1;
		else if(key > a[mid])
			low = mid + 1;
		else
		{
			pos = mid;
			return true;
		}
	}
	return false;
}

3.2 interpolation search

• The basic idea is the search method after comparing the keyword key to be searched with the keyword of the largest and smallest record in the search table.
• For the lookup table with large table length and uniform keyword distribution, the average performance of interpolation lookup algorithm is much better than half lookup.

bool insertSearch(const int* a, int n, int key, int& pos)
{
	int low = 0;
	int high = n - 1;
	while(low <= high)
	{
		int mid = low + (high - low) * (key - a[low]) / (a[high] - a[low]);
		if(key < a[mid])
			high = mid - 1;
		else if(key > a[mid])
			low = mid + 1;
		else
		{
			pos = mid;
			return true;
		}
	}
	return false;
}

3.3 Fibonacci search

• Using the principle of golden section, the average performance is better than half search
• The three kinds of ordered table lookup are essentially different in the selection of partition points. In terms of average performance, Fibonacci lookup is better than half lookup.

bool fibonacciSearch(const int* a, int n, int key, int& pos)
{
	int low = 0;
	int high = n - 1;
	int k = 0;
	while(n > F[k] - 1)		//Calculate the position of n in the Fibonacci sequence
		++k;
	for(int i = n; i < F[k] - 1; ++i)	//Complete the dissatisfied value
		a[i] = a[n];
}

4 binary sort tree BST

• The insertion and deletion efficiency of binary sort tree is good, and the search algorithm can be implemented efficiently for dynamic lookup table.
• Binary sort tree is also called binary search tree. It is either an empty tree or a binary tree with the following properties: if its left subtree is not empty, the values of all nodes on the left subtree are less than the values of its root node; If its right subtree is not empty, the value of all nodes on the right subtree is greater than that of its root node; Its left and right subtrees are also binary sort trees.
• The purpose of constructing binary sort tree is not to sort, but to improve the speed of finding, inserting and deleting keywords.
• The search of binary sort tree is the path from the root node to the node to be searched. The number of comparisons is equal to the depth of the given value node in the binary sort tree, that is, the search performance of binary sort tree depends on the shape of binary sort tree. For an increasing array, the binary sort tree degenerates into a single linked list, which increases the number of layers rapidly. We hope that the binary sort tree is balanced and the depth is the same as that of a complete binary tree, which is [log2n] + 1

//Definition of binary linked list node structure of binary tree
typedef struct _BiTNode
{
	int data;
	struct BiTNode* lchild;
	struct BiTNode* rchild;
} BiTNode;

//Find operation of BST
//f points to the parent of T, and the initial call value is NULL
//p points to the last element of the node if the search is successful
bool searchBst(const BiTNode* T, int key, BiTNode* f, BiTNode* p)
{
	if(T == nullptr)	//The search was unsuccessful
	{
		p = f;
		return false;
	}
	else if(key == T->data)	 //Search succeeded
	{
		p = T
		return true;
	}
	else if(key < T->data)
		return searchBst(T->lchild, key, T, p);		//Continue searching in the left subtree
	else
		return searchBst(T->rchild, key, T, p);		//Continue searching in the right subtree
}

//BST insertion
//The process of constructing BST is the sorting process
//When there is no key in T, insert it and return true; otherwise, return false
bool insertBst(BiTNode* T, int key)
{
	BiTNode p;	//Record the last node accessed
	if(!searchBst(T, key, nullptr, &p))
	{
		BiTNode* s = new BiTNode;
		s->data = key;
		s->lchild = s->rchild = nullptr;
		if(p == nullptr)	
			T = s;	//When there is no root node, insert s as a new root node
		else if(key < p->data)
			p->rchild = s;
		else
			p->lchild = s;
		return true;
	}
	return false;
}

//Delete BST

5 balanced binary tree

5.1 AVL tree

5.2 red black tree