資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ STL 中的二分查詢函式（binary_search、lower_bound 和 upper_bound）
二分查詢是一種搜尋演算法，它透過將元素與陣列的中值進行比較並將陣列進行劃分來搜尋元素。該演算法會重複執行此操作，直到找到該元素。
為了對陣列應用二分查詢，陣列必須已排序。
二分查詢的時間複雜度為**對數**階。因此，程式設計師除了瞭解二分查詢的實現外，還必須瞭解與二分查詢相關的速記方法，以減少編寫該演算法程式碼的時間。本文將討論標準模板庫 (STL) 中包含的與二分查詢演算法相關的函式。
lower_bound - 下界搜尋返回找到元素的位置。
語法
lower_bound(start_pointer , end_pointer, element )
此處，
start_pointer 是一個指標，它儲存搜尋結構起點的記憶體位置。
end_pointer 是一個指標，它儲存搜尋結構終點的記憶體位置。
element 是要使用該函式查詢的元素。
該函式返回要查詢的元素的索引。
返回值可能有多個值 -
如果元素在結構中出現一次，則返回其位置。
如果元素在結構中出現多次，則返回第一個元素的位置。
如果元素不在結構中，則返回比元素大的下一個數字的位置。
任何元素的索引都是透過減去結構的基本位置來找到的。
示例
#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 lower_bound function :";
cout<<"\nCase 1 : When element is present in array but only once ";
cout<<lower_bound(sortedarray.begin() , sortedarray.end(), 7) - sortedarray.begin();
cout<<"\nCase 2 : When element is present more than one times in the array ";
cout<<lower_bound(sortedarray3.begin() , sortedarray3.end(), 7) - sortedarray3.begin();
cout<<"\nCase 3 : When element is not present in the array ";
cout<<lower_bound(sortedarray2.begin() , sortedarray2.end(), 7) - sortedarray2.begin();
}輸出
The position of element 7 found using lower_bound function : Case 1 : When element is present in array but only once 2 Case 2 : When element is present more than one times in the array 2 Case 3 : When element is not present in the array 4
upper_bound - 上界搜尋返回高於傳遞元素的元素的位置。
語法
upper_bound(start_pointer , end_pointer, element)
此處，
start_pointer 是一個指標，它儲存搜尋結構起點的記憶體位置。
end_pointer 是一個指標，它儲存搜尋結構終點的記憶體位置。
element 是要使用該函式查詢的元素。
該函式返回其值大於元素值的元素的索引。
返回值可能有多個值 -
如果元素在結構中出現一次，則返回下一個更高元素的位置。
如果元素在結構中出現多次，則返回最後一個元素的下一個元素的位置。
如果元素不在結構中，則返回比元素大的下一個數字的位置。
任何元素的索引都是透過減去結構的基本位置來找到的。
示例
#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 是一個指標，它儲存搜尋結構終點的記憶體位置。
element 是要使用該函式查詢的元素。
如果元素存在於結構中，則函式返回 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
4K+ 次檢視
