C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++で文字列を二分探索する

文字列のバイナリ検索では、文字列の並べ替えられた配列が与えられ、バイナリ検索アルゴリズムを使用して文字列の配列内の文字列を検索する必要があります。

例

Input : stringArray = {“I”, “Love”, “Programming”, “tutorials”, “point”}.
Element = “programming”
Output : string found at index 3
Explanation : The index of string is 3.
Input : stringArray = {“I”, “Love”, “Programming”, “tutorials”, “point”}.
Element = “coding”
Output : -1 ‘string not found’

二分探索 要素を見つけるために配列の中央を見つけることによって機能する検索手法です。

文字列の配列の場合も、バイナリ検索アルゴリズムは同じままです。ただし、行われる比較は文字列の比較に基づいて行われます。 文字列の比較 文字列の最初の文字を確認して比較します。文字は同じで、次の文字に進みます。

アルゴリズム 
arrString : array of sorted strings
Lower = 0 ; upper = n (length of array)
Element = string that is to be found
Step 1 : while element is not found. Do :
Step 2 : mid = lower + (upper - lower) / 2 ;
Step 3 : if arrString[mid] = element , return mid and exit
Step 4 : if arrString[mid] < element, lower = mid+1
Step 5 : if arrString[mid] > element, upper = mid-1
Step 6 : upper < lower , return -1, exit.

例

#include<bits/stdc++.h>
using namespace std;
int binarySearchString(string arr[], string x, int n) {
   int lower = 0;
   int upper = n - 1;
   while (lower <= upper) {
      int mid = lower + (upper - lower) / 2;
      int res;
      if (x == (arr[mid]))
         res = 0;
      if (res == 0)
         return mid;
      if (x > (arr[mid]))
         lower = mid + 1;
      else
         upper = mid - 1;
   }
   return -1;
}
int main () {
   string arr[] = {"I", "Love", "Programming" , "tutorials" , "point"};
   string x = "Programming";
   int n = 4;
   int result = binarySearchString(arr, x, n);
   if(result == -1)
      cout<<("Element not present");
   else
      cout<<("Element found at index ")<<result;
}

出力

Element found at index 2

  1. C ++プログラムでの二分探索？

    二分探索は、半区間探索、対数探索、または二分探索とも呼ばれ、ソートされた配列内のターゲット値の位置を見つける検索アルゴリズムです。二分探索は、ターゲット値を配列の中央の要素と比較します。それらが等しくない場合、ターゲットが存在できない半分が削除され、残りの半分で検索が続行され、再び中央の要素がターゲット値と比較され、ターゲット値が見つかるまでこれが繰り返されます。残りの半分が空の状態で検索が終了した場合、ターゲットは配列に含まれていません。アイデアは単純ですが、バイナリ検索を正しく実装するには、特に配列の値が範囲内の整数のすべてではない場合、終了条件と中間点の計算に関する微妙な点に注意する必要

  2. C＃での二分探索

    バイナリ検索はソートされた配列で機能します。値は配列の中央の要素と比較されます。同等性が見つからない場合は、値が存在しない半分の部分が削除されます。同様に、残りの半分の部分が検索されます。 これが配列のmid要素です。 62を見つける必要があるとしましょう。そうすると、左側の部分が削除され、右側の部分が検索されます- これらは二分探索の複雑さです- 最悪の場合のパフォーマンス O（log n） ベストケースのパフォーマンス O（1） 平均パフォーマンス O（log n） 最悪の場合のスペースの複雑さ O（1） 例 二分