C言語:データ構造の検索--順序検索

コンセプト:
検索とは、指定された値に基づいて、検索テーブルでキーワードが指定された値に等しいデータ要素を決定することです.
主な検索アルゴリズム:

シーケンステーブル検索:シーケンステーブル検索は無秩序検索に属し、最初のキーワードから、キーワードごとに比較し、与えられたキーワードを検索する.

二分検索:折半検索とも呼ばれ、秩序検索に属し、検索を行う前に検索テーブルをソートし、検索テーブルを秩序化させる必要があり、このように迅速に検索することができる.

補間検索:二分検索の最適化であり、データ内容を中値関係と結びつけることで、検索速度を速める.

Fibonacci検索:秩序検索でもあり、黄金分割原理を利用して実現され、実質的には中値を調整することである.

リニアインデックス検索:インデックスアイテムのセットをリニア構造に整理します.

ハッシュ検索:ハッシュ関数によってストレージ位置を直接取得します.

以下では、各ルックアップのCまたはC++実装、および関連する最適化について、上記の説明の順序で順に説明する.
順序テーブルの検索:
暴力循環によってこの項目とキーワードを項目ごとに比較し、時間の複雑さo(n);
シーケンシャル検索の実装は次のとおりです.

/*             i    ，            */
int search::sequentialSearch(int* a, int n, int key)
{
	int i;
	for (size_t i = 0; i < n; i++)
	{
		if (a[i]==key)
		{
			return i;
		}
	}
	return -1;
}

上のアルゴリズムは実は完璧ではありません.forサイクルでは毎回iとnの値を比較する必要があります.以下に改良版を提出する.

int search::sequentialSearch2(int* a, int n, int key)
{
	if (a[0]==key)
	{
		return 0;
	}
	a[0] = key;
	int i = n - 1;
	while (a[i]!=key)
	{
		i--;
	}
	return i == 0 ? -1 : i;
	
}

上記のバージョンではiとnの比較回数を減らしました.