ですから、私たち皆が知っているように、 二分探索 これは、配列全体を走査することが風変わりな目標ではないデータ構造を扱うときに最も頻繁に適用される検索アルゴリズムの 1 つです。ここでは、中央の要素をチェックし、番号体系に従って役に立たない配列の半分を無視するため、配列をソートする必要があります。基本的に、1 回の比較直後の要素の半分を無視します。したがって、要素が見つかるまで繰り返しを続けるか、それとも要素が配列に存在しないという結論に達するかです。
アルゴリズム:
- x を中央の要素と比較します。
- x が中間要素と一致する場合、中間インデックスを返します。
- Else x が Mid 要素より大きい場合、x は Mid 要素の後の右半分のサブ配列にのみ存在できます。そこで、右半分を再計算します。
- それ以外の場合 (x が小さい場合) は左半分に対して再帰的に実行されます。
例1
ジャワ
Javaは配列に追加します
// Java Program to Illustrate> // Iterative Binary Search> // Main class> // BinarySearch> class> GFG {> >// Method 1> >// Returns index of x> >// if it is present in arr[],> >// else return -1> >int> binarySearch(>int> arr[],>int> x)> >{> >int> l =>0>, r = arr.length ->1>;> >// Checking element in whole array> >while> (l <= r) {> >int> m = l + (r - l) />2>;> >// Check if x is present at mid> >if> (arr[m] == x)> >return> m;> >// If x greater, ignore left half> >if> (arr[m] l = m + 1; // If x is smaller, // element is on left side // so ignore right half else r = m - 1; } // If we reach here, // element is not present return -1; } // Method 2 // Main driver method public static void main(String args[]) { GFG ob = new GFG(); // Input array int arr[] = { 2, 3, 4, 10, 40 }; // Length of array int n = arr.length; // Element to be checked if present or not int x = 10; // Calling the method 1 and // storing result int result = ob.binarySearch(arr, x); // Element present if (result == -1) // Print statement System.out.println('Element not present'); // Element not present else // Print statement System.out.println('Element found at index ' + result); } }> |
C# 日時
>
>出力
Element found at index 3>
時間計算量 : O(log n)
補助スペース :O(1)
個別の SQL をカウントする
例 2
ジャワ
// Java Program to Illustrate Recursive Binary Search> // Importing required classes> import> java.util.*;> // Main class> class> GFG {> >// Method 1> >// Recursive binary search> >// Returns index of x if it is present> >// in arr[l..r], else return -1> >int> binarySearch(>int> arr[],>int> l,>int> r,>int> x)> >{> >// Restrict the boundary of right index> >// and the left index to prevent> >// overflow of indices> >if> (r>= l && l<= arr.length ->1>) {> >int> mid = l + (r - l) />2>;> >// If the element is present> >// at the middle itself> >if> (arr[mid] == x)> >return> mid;> >// If element is smaller than mid, then it can> >// only be present in left subarray> >if> (arr[mid]>x)> >return> binarySearch(arr, l, mid ->1>, x);> >// Else the element can only be present> >// in right subarray> >return> binarySearch(arr, mid +>1>, r, x);> >}> >// We reach here when element is not present in> >// array> >return> ->1>;> >}> >// Method 2> >// Main driver method> >public> static> void> main(String args[])> >{> >// Creating object of above class> >GFG ob =>new> GFG();> >// Custom input array> >int> arr[] = {>2>,>3>,>4>,>10>,>40> };> >// Length of array> >int> n = arr.length;> >// Custom element to be checked> >// whether present or not> >int> x =>10>;> >// Calling above method> >int> result = ob.binarySearch(arr,>0>, n ->1>, x);> >// Element present> >if> (result == ->1>)> >// Print statement> >System.out.println(>'Element not present'>);> >// Element not present> >else> >// Print statement> >System.out.println(>'Element found at index '> >+ result);> >}> }> |
Java文字列の長さ
>
>出力
二分探索
Element found at index 3>
時間計算量 : O(log n)
補助スペース :O(1)