資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ STL 中的二分搜尋函式
二分搜尋是一種搜尋演算法，用於查詢目標值在已排序陣列中的位置。二分搜尋將目標值與已排序陣列的中間元素進行比較。二分搜尋的時間複雜度為 O(1)。這是一個 C++ 程式，其中我們實現了各種。C++ STL 中二分搜尋函式
演算法
Begin Initialize the vector of integer values. The functions are used here: binary_search(start_pointer, end_pointer, value) = Returns true if the value present in array otherwise false. lower_bound(start_pointer, end_pointer, value) = Returns pointer to “position of value” if container contains 1 occurrence of value. Returns pointer to “first position of value” if container contains multiple occurrence of value. Returns pointer to “position of next higher number than value” if container does not contain occurrence of value. upper_bound(start_pointer, end_pointer, value) = Returns pointer to “position of next higher valuethan value” if container contains 1 occurrence of value. Returns pointer to “first position of next higher number than last occurrence of value” if container contains multiple occurrence of value. Returns pointer to “position of next higher number than value” if container does not contain occurrence of value. Print the results. End.
示例程式碼
#include<bits/stdc++.h>
using namespace std;
int main() {
vector<int> a = {6,7,10,14,16,20};
if (binary_search(a.begin(), a.end(), 50))
cout << "50 exists in vector";
else
cout << "50 does not exist";
cout << endl;
if (binary_search(a.begin(), a.end(), 7))
cout << "7 exists in the vector";
else
cout << "7 does not exist";
cout << endl;
cout << "The position of 7 using lower_bound ";
cout << lower_bound(a.begin(), a.end(), 7) - a.begin();
cout << endl;
cout << "The position of 7 using upper_bound ";
cout << upper_bound(a.begin(), a.end(), 7) - a.begin();
cout << endl;
}輸出
50 does not exist 7 exists in the vector The position of 7 using lower_bound 1 The position of 7 using upper_bound 2
更新於: 30-7-2019
918 瀏覽量
廣告