C の二分探索アルゴリズム - C チュートリアル

ソートされた配列内の特定の要素を簡単に見つける方法は、二分探索です。このアルゴリズムの最初のタスクは、ターゲット値を配列の中間要素と比較することです。ターゲット値が中央の要素に含まれている場合、検索は成功したとみなされます。目標値が中央の要素より小さい場合、アルゴリズムは配列の左半分を調べます。目標値が中央の要素より大きい場合、プログラムは配列の右半分をスキャンします。この方法は、目標値または探索範囲がなくなるまで繰り返されます。

使用法：

データベース、検索エンジン、データ処理は、バイナリ検索戦略を使用するアプリケーションのほんの一部です。

特徴:

入力値の配列はソートする必要があります。
このメソッドは反復するたびに検索範囲を半分に縮小し、巨大なデータセットに対して特に効率的になります。
このアルゴリズムの最悪の場合の時間計算量は O (log n) です。
目的の値の検索は、分割統治戦略を使用してプログラムによって行われます。

C で書かれた二分探索アルゴリズムの簡単な例を次に示します。

 #include int binary_search(int arr[], int left, int right, int target) { while (left <= right) { int mid="left" + (right - left) 2; if (arr[mid]="=" target) return mid; } else < left="mid" 1; right="mid" -1; target not found main() arr[]="{1," 3, 5, 7, 9}; n="sizeof(arr)" sizeof(arr[0]); index="binary_search(arr," 0, 1, target); (index="=" -1) printf('target found
'); at %d
', index); 0; pre> <p> <strong>Output:</strong> </p> <pre> Target found at index 2 </pre> <ul> <li>The binary_search function accepts four arguments: the array to search, the left and right search range boundaries, and the target value to look for. The function returns its index if the desired value can be found; else, it returns -1.</li> <li>The main function creates an array arr and a value target. The binary_search function is then used to search the array for the desired value. The function returns the index where the target value was located if it was, the function returns the index at which it was found. Otherwise, the message &apos;Target not found&apos; is displayed.</li> <li>The binary search algorithm&apos;s implementation is basic. We begin by setting the left border to the array&apos;s initial index and the right boundary to the array&apos;s last index. Once the left boundary is less than or equal to the right border, the array is looped through one more time. We use the formula (left + right) / 2 within the loop to calculate the middle index of the search range. This formula computes the integer value of the middle index&apos;s floor.</li> <li>The centre member of the array is contrasted with the target value. We return the index of the middle element if they are equal. We change the right boundary to be one less than the middle index if the desired value is less than the middle element. If not, we adjust the left border so that it is one more than the centre index. We continue doing this until the goal value is obtained or the search space is filled.</li> <li>The temporal complexity of the binary search algorithm, where n is the array size, is O(log n). This is far more efficient than linear search, which has a temporal complexity of O(n), where n is the size of the array.</li> <li>Finally, the binary search technique offers a useful way to locate a particular member in a sorted array. It is easy to build and has an O(log n) time complexity, making it an efficient approach for large datasets.</li> </ul> <h3>Advantages:</h3> <ul> <li>For large datasets, the binary search algorithm is exceptionally efficient, and it is capable of handling a wide range of input sizes.</li> <li>The algorithm is simple to implement in almost all programming languages.</li> </ul> <h3>Disadvantages:</h3> <ul> <li>Before using the binary search technique, the input array must be sorted, which takes more time and memory.</li> <li>The algorithm cannot be applied to unsorted arrays.</li> <li>The algorithm may yield inaccurate results if the input array is not sorted.</li> <li>The binary search algorithm is not appropriate for tiny datasets since the technique&apos;s overhead may outweigh its benefits.</li> </ul> <h2>Conclusion:</h2> <p>A sorted array can be quickly searched for a specific element using the binary search technique. It employs a divide-and-conquer strategy to cut the search range in half with each iteration, allowing it to be highly efficient for large datasets. However, before using the binary search technique, the input array must be sorted, which takes extra time and memory. The binary search algorithm is a sophisticated data processing tool that is widely utilised in various sectors.</p> <hr></=>

binary_search 関数は、検索する配列、左右の検索範囲の境界、検索するターゲット値の 4 つの引数を受け入れます。必要な値が見つかった場合、関数はそのインデックスを返します。それ以外の場合は、-1 を返します。
main 関数は、配列 arr と値のターゲットを作成します。次に、binary_search 関数を使用して、配列内で目的の値を検索します。この関数は、ターゲット値が存在する場合、その値が存在するインデックスを返し、それが見つかったインデックスを返します。それ以外の場合は、「ターゲットが見つかりません」というメッセージが表示されます。
二分探索アルゴリズムの実装は基本的なものです。まず、左境界を配列の最初のインデックスに設定し、右境界を配列の最後のインデックスに設定します。左の境界が右の境界以下になると、配列がもう一度ループされます。ループ内で式 (左 + 右) / 2 を使用して、検索範囲の中央のインデックスを計算します。この式は、中央のインデックスの下限の整数値を計算します。
配列の中心メンバーがターゲット値と対比されます。それらが等しい場合は、中央の要素のインデックスを返します。必要な値が中央の要素より小さい場合は、右側の境界を中央のインデックスより 1 つ小さい値に変更します。そうでない場合は、左側の境界線が中央のインデックスより 1 つ大きくなるように調整します。目標値が取得されるか、検索スペースが埋まるまで、これを続けます。
二分探索アルゴリズムの時間的複雑さ (n は配列サイズ) は O(log n) です。これは、時間的複雑さが O(n) (n は配列のサイズ) である線形検索よりもはるかに効率的です。
最後に、二分探索手法は、ソートされた配列内の特定のメンバーを見つける便利な方法を提供します。構築が簡単で、時間の計算量が O(log n) であるため、大規模なデータセットに対する効率的なアプローチとなります。

利点:

大規模なデータセットの場合、二分探索アルゴリズムは非常に効率的であり、幅広い入力サイズを処理できます。
このアルゴリズムは、ほぼすべてのプログラミング言語で簡単に実装できます。

短所:

二分探索手法を使用する前に、入力配列を並べ替える必要がありますが、これにはより多くの時間とメモリが必要になります。
このアルゴリズムは、ソートされていない配列には適用できません。
入力配列がソートされていない場合、アルゴリズムは不正確な結果を生成する可能性があります。
二分探索アルゴリズムは、手法のオーバーヘッドが利点を上回る可能性があるため、小さなデータセットには適していません。

結論：

二分検索手法を使用すると、ソートされた配列で特定の要素をすばやく検索できます。分割統治戦略を採用し、反復ごとに検索範囲を半分にカットするため、大規模なデータセットに対して非常に効率的になります。ただし、バイナリ検索手法を使用する前に入力配列を並べ替える必要があり、余分な時間とメモリが必要になります。二分探索アルゴリズムは、さまざまな分野で広く利用されている高度なデータ処理ツールです。