サーチ…
バイナリ検索
前書き
バイナリサーチは、分割と征服の検索アルゴリズムです。これは、探索空間内の要素の位置を求めるためにO(log n)時間を使用し、 nは探索空間のサイズである。
バイナリサーチは、ターゲット値と検索スペースの中間値を比較した後、各繰り返しで検索スペースを半分にすることによって機能します。
バイナリ検索を使用するには、検索スペースを何らかの方法で順序付け（並べ替え）する必要があります。 （バイナリ検索のプロパティに違反しないにもかかわらず、重複したエントリ（比較関数に従って等価であるもの）は区別できません。
従来は、比較関数として（<）未満を使用していました。 a <bの場合、trueを返します。 aがb以上でbがa以上であれば、aとbは等しい。
質問の例
あなたはエコノミストですが、かなり悪いです。あなたは、米の平衡価格（すなわち、供給=需要の場合の価格）を見つけるという仕事を与えられます。
価格が高く設定されるほど、供給量が大きくなり、需要量が少なくなることを覚えておいてください
あなたの会社は、市場の力を計算することで、非常に効率的であるとして、米の価格が一定価格に設定されている場合、あなたは即座に米の単位での供給と需要を得ることができp 。
あなたの上司は均衡価格をできるだけ早く求めていますが、均衡価格は10^17正の整数で、その範囲内に正の整数解が1つしかないことが保証されています。あなたがそれを失う前に、あなたの仕事で行く！
関数getSupply(k)とgetDemand(k)を呼び出すことができます。これは、問題に明記されていることを正確に行います。
例の説明
ここに私たちの探索空間は、からである1に10^17 。したがって、線形探索は実行不可能である。
しかし、 kが上がるにつれて、 getSupply(k)が増加し、 getDemand(k)が減少することにgetDemand(k)してください。したがって、任意のx > yに対して、 getSupply(x) - getDemand(x) > getSupply(y) - getDemand(y) 。したがって、この検索スペースは単調で、バイナリ検索を使用できます。
次のpsuedocodeはバイナリ検索の使い方を示しています：
high = 100000000000000000 <- Upper bound of search space
low = 1 <- Lower bound of search space
while high - low > 1
mid = (high + low) / 2 <- Take the middle value
supply = getSupply(mid)
demand = getDemand(mid)
if supply > demand
high = mid <- Solution is in lower half of search space
else if demand > supply
low = mid <- Solution is in upper half of search space
else <- supply==demand condition
return mid <- Found solution
このアルゴリズムは~O(log 10^17)時間で実行されます。これは~O(log S)時間に一般化することができる。ここで、Sは探索空間のサイズであり、なぜならwhileループの繰り返しごとに、探索空間を[低：高]から[低：中]または[中期：高] ）。
再帰によるバイナリ検索のC実装
int binsearch(int a[], int x, int low, int high) {
int mid;
if (low > high)
return -1;
mid = (low + high) / 2;
if (x == a[mid]) {
return (mid);
} else
if (x < a[mid]) {
binsearch(a, x, low, mid - 1);
} else {
binsearch(a, x, mid + 1, high);
}
}
バイナリ検索：ソートされた番号
擬似コードを使用して数値にバイナリ検索を表示するのが最も簡単です
int array[1000] = { sorted list of numbers };
int N = 100; // number of entries in search space;
int high, low, mid; // our temporaries
int x; // value to search for
low = 0;
high = N -1;
while(low < high)
{
mid = (low + high)/2;
if(array[mid] < x)
low = mid + 1;
else
high = mid;
}
if(array[low] == x)
// found, index is low
else
// not found
array [mid]とxを比較することで、早期に復帰しようとしないでください。余分な比較は、コードを遅くするだけです。整数除算が常に丸められることによってトラップされることを避けるために、1を追加する必要があることに注意してください。
興味深いことに、上記のバイナリ検索のバージョンでは、配列中のxの最小出現を見つけることができます。配列にxの重複が含まれている場合、アルゴリズムはif条件に単に足してxの最大の出現を返すように少し修正することができます：
while(low < high)
{
mid = low + ((high - low) / 2);
if(array[mid] < x || (array[mid] == x && array[mid + 1] == x))
low = mid + 1;
else
high = mid;
}
mid = (low + high) / 2を実行する代わりに、Java実装などの実装でmid = low + ((high - low) / 2)を試してみると良いでしょう。非常に大きな入力に対してはオーバーフローします。
線形検索
線形探索は単純なアルゴリズムです。これは、クエリが見つかるまでアイテムをループし、線形アルゴリズムにします。複雑さはO（n）です（nは通過するアイテムの数です）。
なぜO（n）ですか？最悪の場合のシナリオでは、すべてのn個の項目を通過する必要があります。
これは、書籍の中から本を探すことと比較することができます。あなたが望むものが見つかるまで、すべての書籍を読むことができます。
以下はPythonの実装です：
def linear_search(searchable_list, query):
for x in searchable_list:
if query == x:
return True
return False
linear_search(['apple', 'banana', 'carrot', 'fig', 'garlic'], 'fig') #returns True
ラビン・カルプ
Rabin-KarpアルゴリズムまたはKarp-Rabinアルゴリズムは、ハッシュを使用してテキスト内のパターン文字列のいずれか1つを見つける文字列検索アルゴリズムです。平均と最高の実行時間はO（n + m） p）であるが、最悪の場合の時間はO（nm）であり、nはテキストの長さであり、mはパターンの長さである。
文字列照合のためのJavaでのアルゴリズム実装
void RabinfindPattern(String text,String pattern){
/*
q a prime number
p hash value for pattern
t hash value for text
d is the number of unique characters in input alphabet
*/
int d=128;
int q=100;
int n=text.length();
int m=pattern.length();
int t=0,p=0;
int h=1;
int i,j;
//hash value calculating function
for (i=0;i<m-1;i++)
h = (h*d)%q;
for (i=0;i<m;i++){
p = (d*p + pattern.charAt(i))%q;
t = (d*t + text.charAt(i))%q;
}
//search for the pattern
for(i=0;i<end-m;i++){
if(p==t){
//if the hash value matches match them character by character
for(j=0;j<m;j++)
if(text.charAt(j+i)!=pattern.charAt(j))
break;
if(j==m && i>=start)
System.out.println("Pattern match found at index "+i);
}
if(i<end-m){
t =(d*(t - text.charAt(i)*h) + text.charAt(i+m))%q;
if(t<0)
t=t+q;
}
}
}
ハッシュ値を計算する際には、衝突を避けるために素数で除算します。素数で割った後、衝突の可能性は低くなりますが、ハッシュ値が2つの文字列で同じになる可能性があります。私たちは、それが正しいマッチを得ているかどうかを確認するために文字ごとにチェックしなければならない試合を得る。
t =（d *（t - text.charAt（i）* h）+ text.charAt（i + m））％q;
これは、パターンのハッシュ値を再計算するために、最初に一番左の文字を削除してから、新しい文字をテキストに追加します。
線形検索の分析（最悪、平均および最良の場合）
アルゴリズムを分析する3つのケースがあります。
最悪の場合
平均ケース
最良の場合
#include <stdio.h> // Linearly search x in arr[]. If x is present then return the index, // otherwise return -1 int search(int arr[], int n, int x) { int i; for (i=0; i<n; i++) { if (arr[i] == x) return i; } return -1; }/ *上記の関数をテストするドライバプログラム* /
int main() { int arr[] = {1, 10, 30, 15}; int x = 30; int n = sizeof(arr)/sizeof(arr[0]); printf("%d is present at index %d", x, search(arr, n, x)); getchar(); return 0; }
最悪のケース分析（通常は完了）
最悪の場合の分析では、アルゴリズムの実行時間の上限を計算します。最大数の操作が実行されるケースを知る必要があります。リニアサーチでは、検索対象の要素（上記のコードではx）が配列に存在しない場合、最悪の場合が発生します。 xが存在しない場合、search（）関数はそれをarr []のすべての要素と1つずつ比較します。したがって、線形探索の最悪の場合の時間複雑度はΘ（n）であり、
平均ケース分析（時々完了）
平均的なケース分析では、すべての可能な入力を取り、すべての入力の計算時間を計算します。すべての計算値を合計し、合計を入力数で除算します。私たちは事例の分布を知る（または予測する）必要があります。線形探索問題では、すべてのケースが均一に分布していると仮定する（xが配列に存在しない場合を含む）。したがって、すべてのケースを合計し、合計を（n + 1）で除算します。以下は、平均的なケース時間の複雑さの値です。
ベストケース分析（偽）
ベストケースの分析では、アルゴリズムの実行時間の下限を計算します。最小限の操作を実行させるケースを知る必要があります。線形探索問題では、xが第1の位置に存在するときに最良の場合が生じる。最良の場合の操作数は一定です（nに依存しません）。したがって、最良の場合の時間の複雑さはΘ（1）です。ほとんどの場合、アルゴリズムを分析するために最悪の場合の分析を行います。最悪の分析では、良い情報であるアルゴリズムの実行時間の上限を保証します。実際のケースでは、平均的なケース分析は容易ではなく、ほとんど行われません。平均的なケース分析では、すべての可能な入力の数学的分布を知る（または予測する）必要があります。ベストケースの分析は偽です。アルゴリズムの下限を保証しても、最悪の場合のように情報が得られないため、アルゴリズムの実行に数年かかることがあります。
いくつかのアルゴリズムでは、すべての場合が漸近的に同じです。つまり、最悪のケースと最善のケースはありません。たとえば、ソートのマージなどです。マージソートはすべてのケースでΘ（nLogn）操作を行います。他のソートアルゴリズムのほとんどは最悪の場合と最良の場合があります。たとえば、クイックソート（ピボットがコーナー要素として選択されている）の典型的な実装では、入力配列がすでにソートされているときに最悪が発生し、ピボット要素が常に2つの半分に配列を分割するときに最もよく発生します。挿入ソートの場合、配列が逆ソートされ、出力と同じ順序で配列がソートされるときに最悪の場合が発生します。
