logo

TechCodeview

二分探索アルゴリズム – 反復的および再帰的実装

二分探索 アルゴリズム です 検索アルゴリズム ソートされた配列で使用される 検索間隔を繰り返し半分に分割する 。二分探索の考え方は、配列がソートされているという情報を使用し、時間計算量を O(log N) に削減することです。

二分探索 は、ターゲット値の位置を見つけるために使用される検索アルゴリズムです。 並べ替えられた 配列。これは、ターゲット値が見つかるか、間隔が空になるまで、検索間隔を繰り返し半分に分割することによって機能します。対象要素と検索空間の中央値を比較することで、検索間隔が半分になります。



営業四半期

二分探索アルゴリズムを適用するには:

  • データ構造はソートする必要があります。
  • データ構造の任意の要素へのアクセスには一定の時間がかかります。

二分探索アルゴリズム:

このアルゴリズムでは、

  • 次のようにして検索空間を 2 つの半分に分割します。 中間のインデックスを見つける 。

二分探索アルゴリズムで中間インデックス mid を見つける



  • 検索スペースの中央の要素をキーと比較します。
  • キーが中間要素で見つかった場合、プロセスは終了します。
  • キーが中央の要素で見つからない場合は、どちらの半分を次の検索スペースとして使用するかを選択します。
    • キーが中央の要素より小さい場合は、左側が次の検索に使用されます。
    • キーが中央の要素より大きい場合は、右側が次の検索に使用されます。
  • このプロセスは、キーが見つかるか、総検索スペースがなくなるまで続けられます。

二分探索アルゴリズムはどのように機能しますか?

二分探索の仕組みを理解するには、次の図を考慮してください。

配列を考えてみましょう arr[] = {2、5、8、12、16、23、38、56、72、91} 、 そしてその ターゲット = 23 。

最初の一歩： ミッドを計算し、ミッド要素とキーを比較します。キーがmid要素より小さい場合は左に移動し、midより大きい場合は検索スペースを右に移動します。



  • キー (つまり 23) は現在の中間要素 (つまり 16) より大きくなります。検索スペースが右に移動します。

二分探索アルゴリズム : キーと 16 を比較

  • キーは現在の中央 56 よりも小さいです。検索スペースは左に移動します。

二分探索アルゴリズム : キーと 56 を比較

第二段階： キーがmid要素の値と一致する場合、要素が検出され、検索が停止されます。

二分探索アルゴリズム : キーはmidと一致します

二分探索の推奨練習 試してみましょう!

の 二分探索アルゴリズム 次の 2 つの方法で実装できます

  • 反復二分探索アルゴリズム
  • 再帰的二分探索アルゴリズム

以下に、アプローチの疑似コードを示します。

反復二分探索アルゴリズム:

ここでは、while ループを使用して、キーを比較し、検索スペースを 2 つの半分に分割するプロセスを続行します。

反復二分探索アルゴリズムの実装:

ローカル日時Java
C++ 
// C++ program to implement iterative Binary Search #include  using namespace std; // An iterative binary search function. int binarySearch(int arr[], int low, int high, int x) {  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was not present  return -1; } // Driver code int main(void) {  int arr[] = { 2, 3, 4, 10, 40 };  int x = 10;  int n = sizeof(arr) / sizeof(arr[0]);  int result = binarySearch(arr, 0, n - 1, x);  (result == -1)  ? cout << 'Element is not present in array'  : cout << 'Element is present at index ' << result;  return 0; }>
C 
// C program to implement iterative Binary Search #include  // An iterative binary search function. int binarySearch(int arr[], int low, int high, int x) {  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was not present  return -1; } // Driver code int main(void) {  int arr[] = { 2, 3, 4, 10, 40 };  int n = sizeof(arr) / sizeof(arr[0]);  int x = 10;  int result = binarySearch(arr, 0, n - 1, x);  (result == -1) ? printf('Element is not present'  ' in array')  : printf('Element is present at '  'index %d',  result);  return 0; }>
ジャワ 
// Java implementation of iterative Binary Search import java.io.*; class BinarySearch {    // Returns index of x if it is present in arr[].  int binarySearch(int arr[], int x)  {  int low = 0, high = arr.length - 1;  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was  // not present  return -1;  }  // Driver code  public static void main(String args[])  {  BinarySearch ob = new BinarySearch();  int arr[] = { 2, 3, 4, 10, 40 };  int n = arr.length;  int x = 10;  int result = ob.binarySearch(arr, x);  if (result == -1)  System.out.println(  'Element is not present in array');  else  System.out.println('Element is present at '  + 'index ' + result);  } }>
パイソン 
# Python3 code to implement iterative Binary # Search. # It returns location of x in given array arr def binarySearch(arr, low, high, x): while low <= high: mid = low + (high - low) // 2 # Check if x is present at mid if arr[mid] == x: return mid # If x is greater, ignore left half elif arr[mid] < x: low = mid + 1 # If x is smaller, ignore right half else: high = mid - 1 # If we reach here, then the element # was not present return -1 # Driver Code if __name__ == '__main__': arr = [2, 3, 4, 10, 40] x = 10 # Function call result = binarySearch(arr, 0, len(arr)-1, x) if result != -1: print('Element is present at index', result) else: print('Element is not present in array')>
C# 
// C# implementation of iterative Binary Search using System; class GFG {    // Returns index of x if it is present in arr[]  static int binarySearch(int[] arr, int x)  {  int low = 0, high = arr.Length - 1;  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was  // not present  return -1;  }  // Driver code  public static void Main()  {  int[] arr = { 2, 3, 4, 10, 40 };  int n = arr.Length;  int x = 10;  int result = binarySearch(arr, x);  if (result == -1)  Console.WriteLine(  'Element is not present in array');  else  Console.WriteLine('Element is present at '  + 'index ' + result);  } }>
JavaScript 
// Program to implement iterative Binary Search   // A iterative binary search function. It returns // location of x in given array arr[l..r] is present, // otherwise -1  function binarySearch(arr, x) {   let low = 0;  let high = arr.length - 1;  let mid;  while (high>= 低) { 中 = 低 + Math.floor((高 - 低) / 2);    // 要素が中央に存在する場合 // それ自体 if (arr[mid] == x) return mid;    // 要素が mid より小さい場合、 // (arr[mid]> x) high = mid - 1 の場合、要素は左側の部分配列にのみ存在できます。    // それ以外の場合、要素は // 右側の部分配列にのみ存在できます。そうでない場合は low = mid + 1;  // 配列に要素が存在しない場合、ここに到達します return -1; arr =新しい配列(2, 3, 4, 10, 40);  x = 10;  n = 配列の長さ;  結果 = binarySearch(arr, x);   (結果 == -1) ? console.log('要素が配列に存在しません') : console.log ('要素はインデックス ' + 結果に存在します);   // このコードは simranarora5sos と rshuklabbb によって提供されました>>
PHP 
 // PHP program to implement // iterative Binary Search // An iterative binary search  // function function binarySearch($arr, $low, $high, $x) { while ($low <= $high) { $mid = $low + ($high - $low) / 2; // Check if x is present at mid if ($arr[$mid] == $x) return floor($mid); // If x greater, ignore // left half if ($arr[$mid] < $x) $low = $mid + 1; // If x is smaller,  // ignore right half else $high = $mid - 1; } // If we reach here, then  // element was not present return -1; } // Driver Code $arr = array(2, 3, 4, 10, 40); $n = count($arr); $x = 10; $result = binarySearch($arr, 0, $n - 1, $x); if(($result == -1)) echo 'Element is not present in array'; else echo 'Element is present at index ', $result; // This code is contributed by anuj_67. ?>>>
出力 
Element is present at index 3>

時間計算量: O(log N)
補助スペース: ○(1)

再帰的二分探索アルゴリズム:

再帰関数を作成し、検索スペースの中央をキーと比較します。そして、結果に基づいて、キーが見つかったインデックスを返すか、次の検索スペースの再帰関数を呼び出します。

再帰的二分探索アルゴリズムの実装:

C++ 
#include  using namespace std; // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 int binarySearch(int arr[], int low, int high, int x) {  if (high>= 低) { int ミッド = 低 + (高 - 低) / 2;  // 要素が中央に存在する場合 // それ自体 if (arr[mid] == x) return mid;  // 要素が Mid より小さい場合、 // 要素は左の部分配列にのみ存在できる if (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // それ以外の場合、要素は右側の部分配列にのみ存在できます return binarySearch(arr, Mid + 1, high, x);  } } // ドライバーコード int main() { int arr[] = { 2, 3, 4, 10, 40 };  int クエリ = 10;  int n = sizeof(arr) / sizeof(arr[0]);  int result = binarySearch(arr, 0, n - 1, クエリ);  (結果 == -1) ?コート<< 'Element is not present in array'  : cout << 'Element is present at index ' << result;  return 0; }>
C 
// C program to implement recursive Binary Search #include  // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 int binarySearch(int arr[], int low, int high, int x) {  if (high>= 低) { int ミッド = 低 + (高 - 低) / 2;  // 要素が中央に存在する場合 // それ自体 if (arr[mid] == x) return mid;  // 要素が Mid より小さい場合、 // 要素は左の部分配列にのみ存在できる if (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // それ以外の場合、要素は右側の部分配列にのみ存在できます return binarySearch(arr, Mid + 1, high, x);  // 配列に要素が存在しない場合、ここに到達します return -1; } // ドライバーコード int main() { int arr[] = { 2, 3, 4, 10, 40 };  int n = sizeof(arr) / sizeof(arr[0]);  int x = 10;  int 結果 = binarySearch(arr, 0, n - 1, x);  (結果 == -1) ? printf('要素が配列に存在しません') : printf('要素はインデックス %d に存在します', result);  0を返します。 }>>
ジャワ 
// Java implementation of recursive Binary Search class BinarySearch {  // Returns index of x if it is present in arr[low..  // high], else return -1  int binarySearch(int arr[], int low, int high, int x)  {  if (high>= 低) { int ミッド = 低 + (高 - 低) / 2;  // 要素がその中間に存在する場合 // if (arr[mid] == x) return mid;  // 要素が Mid より小さい場合、 // 要素は左の部分配列にのみ存在できる if (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // それ以外の場合、要素は右側の部分配列にのみ存在できます return binarySearch(arr, Mid + 1, high, x);  } // 要素が存在しない場合にここに到達します // 配列に return -1;  } // ドライバー コード public static void main(String args[]) { BinarySearch ob = new BinarySearch();  int arr[] = { 2, 3, 4, 10, 40 };  int n = arr.length;  int x = 10;  int result = ob.binarySearch(arr, 0, n - 1, x);  if (result == -1) System.out.println( '要素が配列内に存在しません');  else System.out.println( '要素はインデックス ' + result);  } } /* このコードは Rajat Mishra によって寄稿されました */>>
パイソン 
# Python3 Program for recursive binary search. # Returns index of x in arr if present, else -1 def binarySearch(arr, low, high, x): # Check base case if high>= low:mid = low + (high - low) // 2 # 要素が中央自体に存在する場合 if arr[mid] == x: return Mid # 要素が Mid より小さい場合、 # 存在することのみ可能左側の部分配列 elif arr[mid]> x: return binarySearch(arr, low, mid-1, x) # それ以外の場合、要素は右側の部分配列にのみ存在できます。それ以外の場合: return binarySearch(arr, Mid + 1, high, x) ) # 要素が配列に存在しません else: return -1 # ドライバー コード if __name__ == '__main__': arr = [2, 3, 4, 10, 40] x = 10 # 関数呼び出しの結果 = binarySearch( arr, 0, len(arr)-1, x) if result != -1: print('要素はインデックスに存在します', result) else: print('要素は配列に存在しません')>
C# 
// C# implementation of recursive Binary Search using System; class GFG {  // Returns index of x if it is present in  // arr[low..high], else return -1  static int binarySearch(int[] arr, int low, int high, int x)  {  if (high>= 低) { int ミッド = 低 + (高 - 低) / 2;  // 要素がその中間に存在する場合 // if (arr[mid] == x) return mid;  // 要素が Mid より小さい場合、 // 要素は左の部分配列にのみ存在できる if (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // それ以外の場合、要素は右側の部分配列にのみ存在できます return binarySearch(arr, Mid + 1, high, x);  } // 要素が存在しない場合にここに到達します // 配列に return -1;  } // ドライバーコード public static void Main() { int[] arr = { 2, 3, 4, 10, 40 };  int n = arr.Length;  int x = 10;  int result = binarySearch(arr, 0, n - 1, x);  if (result == -1) Console.WriteLine( '要素が arrau に存在しません');  else Console.WriteLine('要素はインデックス ' + 結果に存在します);  } } // このコードは Sam007 によって提供されました。>>
JavaScript 
// JavaScript program to implement recursive Binary Search // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 function binarySearch(arr, low, high, x){  if (high>= 低) { let mid = 低 + Math.floor((高 - 低) / 2);  // 要素が中央に存在する場合 // それ自体 if (arr[mid] == x) return mid;  // 要素が Mid より小さい場合、 // 要素は左の部分配列にのみ存在できる if (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // それ以外の場合、要素は右側の部分配列にのみ存在できます return binarySearch(arr, Mid + 1, high, x);  // 配列に要素が存在しない場合、ここに到達します return -1; arr = [ 2, 3, 4, 10, 40 ]; x = 10 とします。 let n = arr.length let result = binarySearch(arr, 0, n - 1, x); (結果 == -1) ? console.log( '配列に要素が存在しません') : console.log('インデックス ' に要素が存在します +result);>>
PHP 
 // PHP program to implement // recursive Binary Search // A recursive binary search // function. It returns location // of x in given array arr[low..high]  // is present, otherwise -1 function binarySearch($arr, $low, $high, $x) { if ($high>= $low) { $mid = ceil($low + ($high - $low) / 2); // 要素が存在する場合 // それ自体の中央にある if ($arr[$mid] == $x) return Floor($mid); // 要素が Mid より小さい場合、 // 左の部分配列にのみ存在できます if ($arr[$mid]> $x) return binarySearch($arr, $low, $mid - 1, $x ); // それ以外の場合、要素は // 右側のサブ配列にのみ存在できます return binarySearch($arr, $mid + 1, $high, $x); } // 配列に要素が // 存在しない場合、ここに到達します return -1; } // ドライバーコード $arr = array(2, 3, 4, 10, 40); $n = カウント($arr); $x = 10; $result = binarySearch($arr, 0, $n - 1, $x); if(($result == -1)) echo '要素が配列内に存在しません'; else echo '要素はインデックス ' に存在します', $result; ?>>>
出力 
Element is present at index 3>
  • 時間計算量:
    • 最良のケース: O(1)
    • 平均的なケース: O(log N)
    • 最悪の場合: O(log N)
  • 補助スペース: O(1)、再帰呼び出しスタックが考慮される場合、補助空間は O(logN) になります。
  • 二分探索は、ニューラル ネットワークをトレーニングしたり、モデルに最適なハイパーパラメータを見つけたりするためのアルゴリズムなど、機械学習で使用されるより複雑なアルゴリズムの構成要素として使用できます。
  • レイ トレーシングやテクスチャ マッピングのアルゴリズムなど、コンピューター グラフィックスの検索に使用できます。
  • データベースの検索に使用できます。
  • 二分探索は、特に大規模な配列の場合、線形探索よりも高速です。
  • 内挿検索や指数検索など、同様の時間計算量を持つ他の検索アルゴリズムよりも効率的です。
  • 二分探索は、ハード ドライブやクラウドなどの外部メモリに保存されている大規模なデータセットの検索に適しています。
  • 配列はソートされる必要があります。
  • 二分検索では、検索対象のデータ構造が連続したメモリ位置に格納されている必要があります。
  • 二分探索では、配列の要素が比較可能であることが必要です。つまり、要素を順序付けできる必要があります。

二分探索に関するよくある質問 (FAQ):

1. 二分探索とは何ですか?

二分探索は、ソートされた配列内でターゲット値を見つけるための効率的なアルゴリズムです。これは、検索間隔を繰り返し半分に分割することで機能します。

2. 二分探索はどのように機能しますか?

二分探索では、ターゲット値と配列の中央の要素が比較されます。それらが等しい場合、検索は成功します。ターゲットが中央の要素より小さい場合、検索は配列の下半分で継続されます。ターゲットが大きい場合、検索は上半分で継続されます。このプロセスは、ターゲットが見つかるか、検索間隔が空になるまで繰り返されます。

3. 二分探索の時間計算量はどれくらいですか?

二分探索の時間計算量は O(log2n)、n は配列内の要素の数です。これは、検索間隔のサイズが各ステップで半分になるためです。

4. 二分探索の前提条件は何ですか?

二分探索では、配列が昇順または降順でソートされている必要があります。配列がソートされていない場合、二分検索を使用して配列内の要素を検索することはできません。

5. 配列が二分探索用にソートされていない場合はどうなりますか?

配列がソートされていない場合、二分検索で間違った結果が返される可能性があります。配列のソートされた性質に基づいて、配列のどの半分を検索するかを決定します。

6. 二分検索は数値以外のデータにも適用できますか?

はい、要素の順序が定義されている限り、二分検索は数値以外のデータにも適用できます。たとえば、文字列をアルファベット順に検索するために使用できます。

7. 二分探索の一般的な欠点は何ですか?

二分探索の欠点は、ターゲット要素がどの半分にあるかを決定するために入力配列をソートする必要があることです。したがって、ソートされていない配列の場合は、二分探索を適用する前に配列をソートする必要があります。

8. 二分探索はどのような場合に使用する必要がありますか?

ソートされた配列内でターゲット値を検索する場合、特に配列のサイズが大きい場合は、二分探索を使用する必要があります。線形検索アルゴリズムと比較して、大規模なデータセットの場合に特に効率的です。

9. 二分探索は再帰的に実装できますか?

はい、二分探索は反復的および再帰的に実装できます。再帰的な実装ではコードがより簡潔になることがよくありますが、再帰的なスタック スペースや関数呼び出しによりオーバーヘッドがわずかに高くなる可能性があります。

10. ソートされた配列内での検索には、常に二分探索が最適な選択ですか?

二分検索はソートされた配列内での検索には非常に効率的ですが、小さなデータセットを扱う場合や配列が頻繁に変更される場合など、他の検索アルゴリズムの方が適切な特定のケースが存在する場合があります。

関連記事：

  • 問題のある解答チュートリアルの二分探索
  • 線形探索と二分探索
  • 二分探索の問題を特定して解決するにはどうすればよいですか?