binary_search()作為STL函數 (binary_search() as a STL function)
Syntax:
句法：
bool binary_search (
ForwardIterator first,
ForwardIterator last,
const T& value);
Where,
哪里，
ForwardIterator first = iterator to start of the range
ForwardIterator first =迭代器開始范圍
ForwardIterator last =iterator to end of the range
ForwardIterator last =迭代器到范圍的結尾
T &value = reference to searching element which is of datatype T, T can be any inbuilt datatype or user-defined data type
T＆value =對數據類型為T的搜索元素的引用， T可以是任何內置數據類型或用戶定義的數據類型
Return type: bool
返回類型： bool
True - if element found in the range
True-如果在范圍內找到元素
False - If the element not found in the range
False-如果在范圍內找不到元素
The above syntax is used to compare elements using standard comparison operators. Two elements a & b are said to be equal if (!(a<b) && !(a>b)).
上面的語法用于使用標準比較運算符比較元素。 if(！(a <b)&&！(a> b))的兩個元素a和b相等。
We can also define the user-defined comparator for comparing. The syntax with user-defined comparator is like below:
我們還可以定義用戶定義的比較器進行比較。 用戶定義的比較器的語法如下：
bool binary_search(
ForwardIterator first,
ForwardIterator last,
const T& val,
Comparator comp);
Using the above syntax two elemnts a & b would be equal if (!comp(a<b) && !comp(a>b)).
使用以上語法， 如果(！comp(a <b)&&！comp(a> b))，則兩個元素a和b相等。
1)使用默認比較器 (1) Using default comparator)
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<int> arr{ 3, 2, 1, 4, 5, 6, 7 };
//tp perform binary search we need sorted
//input array
sort(arr.begin(), arr.end());
int search_element = 4;
//ForwardIterator first=arr.begin()
//ForwardIterator last=arr.end()
//const T& val=search_element
if (binary_search(arr.begin(), arr.end(), search_element)) {
cout << "search_element " << search_element << " found\n";
}
else
cout << "search_element" << search_element << " not found\n";
search_element = 7;
//ForwardIterator first=arr.begin()
//ForwardIterator last=arr.begin()+arr.size()-1
//const T& val=search_element
if (binary_search(arr.begin(), arr.begin() + arr.size() - 1, search_element)) {
cout << "search_element " << search_element << " found\n";
}
else
cout << "search_element " << search_element << " not found\n";
return 0;
}
Output:
輸出：
search_element 4 found
search_element 7 not found
In the above program, we have checked to cases and have used the default comparator. No need to mention, since this uses the binary search algorithm for searching, we need to feed sorted array only.
在上面的程序中，我們檢查了案例并使用了默認的比較器。 無需提及，因為它使用二進制搜索算法進行搜索，所以我們僅需要提供已排序的數組。
So as a pre-requisite we sorted the array. The sorted array is: [1,2,3,4,5,6,7]
因此，作為前提條件，我們對數組進行了排序。 排序后的數組是： [1,2,3,4,5,6,7]
Then for the first case, our range is the entire vector, and it returned true is since it finds the searched element 4.
那么對于第一種情況，我們的范圍是整個向量，并且由于找到了要搜索的元素4而返回true。
For the second case, our range is [1-6] as we mentioned the end iterator as arr.begin()+arr.size()-1 which leaves the last element 7. So searched element 7 is not found.
對于第二種情況，我們的范圍是[1-6]，因為我們提到的最終迭代器為arr.begin()+ arr.size()-1 ，它保留了最后一個元素7 。 因此未找到搜索到的元素7 。
2)使用用戶定義的比較器功能 (2) Using user-defined comparator function)
Here we have taken a use case where we have student details for five students. By using the user-defined comparator we have checked whether there is a student with the specified marks or not.
在這里，我們使用了一個用例，其中有五個學生的學生詳細信息。 通過使用用戶定義的比較器，我們檢查了是否有指定分數的學生。
#include <bits/stdc++.h>
using namespace std;
class student {
int score;
int roll;
string name;
public:
student()
{
score = 0;
roll = 0;
name = "";
}
student(int sc, int ro, string nm)
{
score = sc;
roll = ro;
name = nm;
}
int get_score()
{
return score;
}
int get_roll()
{
return roll;
}
string get_name()
{
return name;
}
};
//comparator for sorting
bool myfunc(student a, student b)
{
if (a.get_score() < b.get_score()) //no swap
return true;
else //swap
return false;
}
//comparator for binary search
//match found if !mycomp(a,b) && !mycomp(b,a)
bool mycomp(student a, student b)
{
if (a.get_score() < b.get_score())
return true;
return false;
}
int main()
{
vector<student> arr(5);
//1st student
arr[0] = student(80, 5, "XYZ"); //roll 5, marks 80
//2nd student
arr[1] = student(70, 10, "INC"); //roll 10, marks 70
//3rd student
arr[2] = student(85, 7, "HYU"); //roll 7, marks 85
//4th student
arr[3] = student(83, 1, "EFG"); //roll 1, marks 83
//5th student
arr[4] = student(81, 11, "ABC"); //roll 11, marks 81
//sort based on marks
//user-defined compartor=myfunc to sort
sort(arr.begin(), arr.end(), myfunc);
//find if any student exists who scored 81
student t1(81, -1, ""); //dummy search element just to search the student marks
if (binary_search(arr.begin(), arr.end(), t1, mycomp))
cout << "Student with marks 81 exists\n";
else
cout << "Student with marks 81 doesn't exist\n";
//find if any student exists who scored 75
student t2(75, -1, ""); //dummy search element just to search the student marks
if (binary_search(arr.begin(), arr.end(), t2, mycomp))
cout << "Student with marks 75 exists\n";
else
cout << "Student with marks 75 doesn't exist\n";
return 0;
}
Output:
輸出：
Student with marks 81 exists
Student with marks 75 doesn't exist
Here we have first sorted the student vector using the user-defined comparator function. We have defined a separate comparator for binary search, though both have the same body. We have specified just to underline the factor that both comparators are not used in the same way. In case of searching, there is a match b/w T a and T b (T be the datatype) if !comp(a,b) && !comp(b, a) where a is element from the vector and b is the searching element.
在這里，我們首先使用用戶定義的比較器函數對學生向量進行了排序。 我們為二進制搜索定義了一個單獨的比較器，盡管兩者具有相同的主體。 我們僅指定要強調兩個比較器未以相同方式使用的因素。 在搜索的情況下， 如果！comp(a，b)&&！comp(b，a)匹配b / w T a和T b(T為數據類型) ，其中a是向量中的元素， b是搜索元素。
So in this article, you saw how efficiently we can use binary_search to search elements within a range, no matter what kind of object it is. Even for the user-defined datatype, we can do by using a user-defined comparator as shown above. But, the main thing to remember is that the input list must be sorted(based on the key). For example, as we were searching for the marks, we sorted the student list based on marks.
因此，在本文中，您看到了無論使用哪種對象，我們都能有效地使用binary_search搜索范圍內的元素。 即使對于用戶定義的數據類型，我們也可以通過使用用戶定義的比較器來完成，如上所示。 但是，要記住的主要事情是必須對輸入列表進行排序(基于鍵)。 例如，在搜索標記時，我們根據標記對學生列表進行了排序。
翻譯自: https://www.includehelp.com/stl/std-binary_search-in-cpp.aspx
為null的日子)
)
