C++ STL 二叉搜尋

Harshit Jindal 2023年10月12日

C++ C++ Algorithm

C++ STL binary_search() 概述
二叉搜尋的 C++ 程式

C++ 為我們提供了一個現成的函式 binary_search()，這樣我們就不用自己去實現這個函式了。它是一種非常簡單的使用和有效實現的方法，而且不容易出錯。

C++ STL `binary_search()` 概述

語法

DEFAULT
    : template <class ForwardIterator, class T>
      bool
      binary_search(ForwardIterator first, ForwardIterator last, const T& val);

CUSTOM COMPARISON FUNCTION
    : template <class ForwardIterator, class T, class Compare>
      bool
      binary_search(ForwardIterator first, ForwardIterator last, const T& val,
                    Compare comp);

這裡，T 可以是以下任何一種：int、float、short、long、byte、char、double，甚至使用者定義的 Object。

它使用二叉搜尋演算法檢查 [first, last) 內的元素是否與目標元素 X 匹配。預設情況下，它使用小於操作符來比較元素，但我們也可以提供我們自己的自定義 comp，如上面給出的第二個模板所述。

引數


`first`	指向給定陣列範圍內第一個元素的前向迭代器。
`last`	指向給定陣列範圍內最後一個元素的前向迭代器。
`comp`	一個使用者定義的二進位制謂詞函式，接受兩個正向迭代器作為引數，如果兩個引數以正確的順序出現，則返回 `true`。它不修改任何引數，並遵循嚴格的弱排序來排列元素。
`val`	我們在給定陣列範圍內搜尋的目標元素。

返回值

如果找到目標元素，則返回 true，否則返回 false。

二叉搜尋的 C++ 程式

#include <bits/stdc++.h>
using namespace std;

int main() {
  vector<int> v = {1, 2, 3, 4, 5, 6};

  if (binary_search(v.begin(), v.end(), 5)) {
    cout << "Element found" << endl;
  } else {
    cout << "Element not found" << endl;
  }

  return 0;
}

作者： Harshit Jindal

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

C++ STL binary_search() 概述

語法

引數

返回值

二叉搜尋的 C++ 程式

相關文章 - C++ Algorithm

C++ STL `binary_search()` 概述