STL系列(二)二分查找

函式:binary_search

• 內容里如有未知文章中未提到的函式參考請查看上一篇文章STL系列(一)sort用法
• 本期內容會出現大量相似但不相同的話,認真閱讀,注意對比,加深記憶,不要覺得內容重復而心煩
• 注意加粗陳述句
• 有疑問留言 or 評論

用法一(基本查找)

內容:

        binary_search( 陣列名 + n1, 陣列名 + n2, 值 )
    
        n1和n2都是 int 型別的運算式 , 可以包含變數

        如果n1 = 0,則 + n1 可以不寫

        查找區間為下標范圍為[n1,n2)的元素, 下標為n2的元素不在查找區間內 
                   
        在該區間內查找"等于"值的元素, 回傳值為true(找到) 或false(沒找到)
          
        "等于"的含義: a 等于 b <==> a < b和b < a都不成立

范例:

	int a[] = { 12,45,3,98,21,7 };
	sort(a, a + 6);
	Print(a, 6);       //結果: 3,7,12,21,45,98
	cout << "Result : " << binary_search(a, a + 6, 12) << endl;  //Result : 1
	cout << "Result : " << binary_search(a, a + 6, 77) << endl;  //Result : 0

• 在使用STL二分查找前要先用sort排序;

用法二 (自定義排序規則查找)

內容:

在用自定義排序規則排好序的 , 元素為任意的T型別得陣列進行二分查找

binary_search(陣列名 +n1 , 陣列名 + n2 , 值 , 排序規則結果名() );

n1和n2都是int型別得運算式,可以包含變數

如果 n1 = 0 , 則 + n1可以不寫

查找區間為下標范圍[n1,n2)的元素 , 下標為n2的元素不在查找區間內

在該區間內查找"等于"值的元素, 回傳值為true(找到) 或false(沒找到)

*查找時的排序規則,必須和排序時的規則一致!

"等于"的含義:  a 等于 b <==> "a必須在b前面"和"b必須在a前面"都不成立

重要的事多次強調加深印象! 不是水文章!

范例:

    int a[] = { 12,45,3,98,21,7 };
	sort(a, a + 6, Rule1());   //按從小到大排序(此處使用Rule1規則進行排序)
	Print(a, 6);               // 21,12,3,45,7,98
	cout << "Result : " << binary_search(a, a + 6, 7) << endl;          //Result : 0
	cout << "Result : " << binary_search(a, a + 6, 8, Rule1()) << endl; //Result : 1
	return 0;

上面代碼第4行為錯誤代碼

此處編譯器回傳值為0并不是意味著沒查到!

binary_search()二分查找規則必須與排序規則一致, 否則回傳值 沒有意義

完整代碼:(包含自定義函式)

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
struct Rule1 {
	bool operator()(const int& a1, const int& a2)const {
		return a1 % 10 < a2 % 10;
	}
};

void Print(int a[], int size);

int main() {
	int a[] = { 12,45,3,98,21,7 };
	sort(a, a + 6);
	Print(a, 6);
	cout << "Result : " << binary_search(a, a + 6, 12) << endl;
	cout << "Result : " << binary_search(a, a + 6, 77) << endl;
	sort(a, a + 6, Rule1());//按從小到大排序
	Print(a, 6);
	cout << "Result : " << binary_search(a, a + 6, 7) << endl;
	cout << "Result : " << binary_search(a, a + 6, 8, Rule1()) << endl;
	return 0;
}

void Print(int a[], int size) {
	int i;
	for (i = 0; i < size - 1; i++) {
		cout << a[i] << ",";
	}
	cout << a[i];
	cout << endl;
}

函式lower_bound

用法一(查找下界)

在對元素型別為 T 的從小到大排好序的基本資料型別中進行查找

T * lower_bound(陣列名 + n1 , 陣列名 + n2 , 值);

回傳一個指標 T * p;

*p 是查找區間里下標最小的,大于等于"值"的元素. 如果找不到, p 指向下標為n2 的元素

注意:n2不在查詢范圍內哦!

范例:

	int a[NUM] = { 12,5,3,5,98,21,7 };
	sort(a, a + NUM);
	Print(a, NUM);  // 結果: 3,5,5,7,12,21,98
	int* p1 = lower_bound(a, a + NUM, 5); //范圍整個陣列,p1指向下標最小的 大于等于5的元素
	cout << " p1指向的內容:"<< *p1 << "  下標:" << p1 - a << endl;   // 結果:5,1

用法二(自定義規則查找下界)

在對元素型別為 T ,按照自定義排序規則排好序的陣列中進行查找

T * lower_bound(陣列名 + n1 , 陣列名 + n2 , 值 , 排序規則結構名());

回傳一個指標 T * p;

*p 是查找區間里下標最小的,按自定義排序規則 , 可以 排在"值"后面的元素. 如果找不到,p指向下標為n2的元素

注意:n2不在查詢范圍內哦!

范例:

	int a[NUM] = { 12,5,3,5,98,21,7 };
    sort(a, a + NUM, Rule1());
	Print(a, NUM); // 結果 :21,12,3,5,5,7,98
	cout << *lower_bound(a, a + NUM, 16, Rule1()) << endl;    // 結果 : 7 (輸出元素值)
	cout << lower_bound(a, a + NUM, 25, Rule1()) - a << endl; // 結果 : 3 (輸出下標值)

后面內容可以自己試著分析原因

函式upper_bound

用法一(查找上界)

內容:

在元素型別為 T 的從小到大排好序的基本型別得陣列中進行查找

T * upper_bound(陣列名 + n1 , 陣列名 + n2 , 值);

回傳一個指標 T * p;

*p 是查找區間里下標最小的, 大于"值"的元素. 如果找不到, p指向下標為n2 的元素

范例:

	int a[NUM] = { 12,5,3,5,98,21,7 };
	sort(a, a + NUM);
    Print(a, NUM);  // 結果: 3,5,5,7,12,21,98
    int* p2 = upper_bound(a, a + NUM, 5); //范圍整個陣列,p2指向下標最小的 大于5的元素
	cout << *p2 << endl;  // 結果:7
	cout << *upper_bound(a, a + NUM, 13) << endl;//查找大于13的下標最小的元素值 結果 :21

用法二(自定義規則查找上界)

內容:

在元素為任意的T型別 , 按照自定義排序規則排好序的陣列中進行查找

T * upper_bound(陣列名 + n1 , 陣列名 + n2 , 值 , 排序規則結構體());

回傳一個指標 T * p;

*p 是查找區間內下標最小的, 按自定義排序規則, **必須 **排在 “值” 后面的元素 . 如果找不到 ,p指向下標為n2的元素

范例:

	int a[NUM] = { 12,5,3,5,98,21,7 };
    sort(a, a + NUM, Rule1());
	Print(a, NUM); // 結果 :21,12,3,5,5,7,98
	cout << *lower_bound(a, a + NUM, 16, Rule1()) << endl;    // 結果 : 7 (輸出元素值)
	cout << lower_bound(a, a + NUM, 25, Rule1()) - a << endl; // 結果 : 3 (輸出下標值)
	cout << upper_bound(a, a + NUM, 18, Rule1()) - a << endl; // 結果 : 7 (無意義)(個位數大于8無法找到)(找不到時回傳終點元素)
	if (upper_bound(a, a + NUM, 18, Rule1()) == a + NUM)
	cout << "not found" << endl;     // ==>not found;
	cout << *upper_bound(a, a + NUM, 5, Rule1()) << endl;      // 結果 : 7 (自己想想原因)
	cout << *upper_bound(a, a + NUM, 4, Rule1()) << endl;      // 結果 : 5

完整代碼:

#include<iostream>
#include<algorithm>
#include<cstring>

#define NUM 7
using namespace std;
struct Rule1 {
	bool operator()(const int& a1, const int& a2)const {
		return a1 % 10 < a2 % 10;
	}
};
void Print(int a[], int size);

int main() {
	int a[NUM] = { 12,5,3,5,98,21,7 };
	sort(a, a + NUM);
	Print(a, NUM);  // 結果: 3,5,5,7,12,21,98
	int* p1 = lower_bound(a, a + NUM, 5); //范圍整個陣列,p1指向下標最小的 大于等于5的元素
	cout << " p1指向的內容:"<< *p1 << "  下標:" << p1 - a << endl;   // 結果:5,1
	int* p2 = upper_bound(a, a + NUM, 5); //范圍整個陣列,p2指向下標最小的 大于5的元素
	cout << *p2 << endl;  // 結果:7
	cout << *upper_bound(a, a + NUM, 13) << endl;//查找大于13的下標最小的元素值 結果 :21
	sort(a, a + NUM, Rule1());
	Print(a, NUM); // 結果 :21,12,3,5,5,7,98
	cout << *lower_bound(a, a + NUM, 16, Rule1()) << endl;    // 結果 : 7 (輸出元素值)
	cout << lower_bound(a, a + NUM, 25, Rule1()) - a << endl; // 結果 : 3 (輸出下標值)
	cout << upper_bound(a, a + NUM, 18, Rule1()) - a << endl; // 結果 : 7 (無意義)(個位數大于8無法找到)(找不到時回傳終點元素)
	if (upper_bound(a, a + NUM, 18, Rule1()) == a + NUM)
		cout << "not found" << endl;     // ==>not found;
	cout << *upper_bound(a, a + NUM, 5, Rule1()) << endl;      // 結果 : 7 (自己想想原因)
	cout << *upper_bound(a, a + NUM, 4, Rule1()) << endl;      // 結果 : 5
	return 0;
}

void Print(int a[], int size) {
	int i;
	for (i = 0; i < size - 1; i++) {
		cout << a[i] << ",";
	}
	cout << a[i];
	cout << endl;
}