C ++ STLのバイナリ検索関数（binary_search、lower_bound、upper_bound）

要素が構造内で1回出現した場合、次に高い要素の位置が返されます。

要素が構造内で複数回出現する場合、最後の要素の次の要素の位置が返されます。

要素が構造体に存在しない場合、要素より次に大きい番号の位置が返されます。

インデックス 任意の要素のは、構造の基本位置を引くことによって求められます。

例

#include<bits/stdc++.h>
using namespace std;
int main(){
   vector<int> sortedarray = {2 , 5, 7, 8 , 15, 20 };
   vector<int> sortedarray2 = {2, 3, 4, 6 , 9 , 23 };
   vector<int> sortedarray3 = {2 , 5, 7, 7 , 15, 20 };
   cout<<"The position of element 7 found using upper_bound function :";
   cout<<"\nCase 1 : When element is present in array but only once ";
   cout<<upper_bound(sortedarray.begin() , sortedarray.end(), 7) - sortedarray.begin();
   cout<<"\nCase 2 : When element is present more than one times in the array ";
   cout<<upper_bound(sortedarray3.begin() , sortedarray3.end(), 7) - sortedarray3.begin();
   cout<<"\nCase 3 : When element is not present in the array ";
   cout<<upper_bound(sortedarray2.begin() , sortedarray2.end(), 7) - sortedarray2.begin();
}

出力

The position of element 7 found using upper_bound function :
Case 1 : When element is present in array but only once 3
Case 2 : When element is present more than one times in the array 4
Case 3 : When element is not present in the array 4

binary_search 要素が構造体に存在するかどうかをチェックする関数です。

構文

binary_search(start_pointer , end_pointer, element)

ここで

start_pointer 検索構造の開始点のメモリ位置を保持するポインタです。

end_pointer 検索構造のエンドポイントのメモリ位置を保持するポインタです。

要素 関数を使用して検出される要素です。

要素が構造体に存在する場合、関数はtrueを返します。それ以外の場合は、falseを返します。

例

#include<bits/stdc++.h>
using namespace std;
int main(){
   vector<int> sortedarray = {6, 15, 21, 27, 39, 42};
   cout<<"The element to be found in the array is 21\n" ;
   if(binary_search(sortedarray.begin(), sortedarray.end(), 21))
      cout<<"The element is found";
   else
      cout<<"The element is not found";
      cout<<"\nThe element to be found in the array is 5\n" ;
   if(binary_search(sortedarray.begin(), sortedarray.end(), 5))
      cout<<"The element is found";
   else
      cout<<"The element is not found";
}

出力

The element to be found in the array is 21
The element is found
The element to be found in the array is 5
The element is not found