Upper Bound และ Lower Bound สำหรับเวกเตอร์เรียงลำดับไม่เพิ่ม (Non-increasing) ใน C++

บทความนี้จะอธิบายการใช้ vector::upper_bound() และ vector::lower_bound() สำหรับอาร์เรย์ที่เรียงลำดับแบบไม่เพิ่ม (non-increasing order) ใน C++ STL

เวกเตอร์ (Vector) คล้ายกับอาร์เรย์ไดนามิก ที่สามารถปรับขนาดได้เองเมื่อมีการเพิ่มหรือลบข้อมูลในคอนเทนเนอร์

ในเวกเตอร์ที่เรียงลำดับไม่เพิ่ม (มากไปน้อย):

• Lower Bound – ส่งคืนอีเทอเรเตอร์ชี้ไปที่องค์ประกอบแรกที่ ไม่เกิน ค่าที่กำหนด (คือ ค่า <= key)
• Upper Bound – ส่งคืนอีเทอเรเตอร์ชี้ไปที่องค์ประกอบแรกที่ น้อยกว่า ค่าที่กำหนด (คือ ค่า < key)

ตัวอย่าง Input/Output

ตัวอย่างที่ 1

Input:

30 30 30 20 20 20 10 10

Output:

Lower bound of 20 = 3
Upper bound of 20 = 6

คำอธิบาย: ค่า 20 เริ่มที่ index 3 (lower bound) และค่าตัวแรกที่น้อยกว่า 20 คือ 10 ที่ index 6 (upper bound)

ตัวอย่างที่ 2

Input:

9 9 8 8 8 7 7 7 6 6 6 6

Output:

Lower bound of 7 = 5
Upper bound of 7 = 8

ค่าที่ส่งคืน

ส่งคืนอีเทอเรเตอร์ชี้ไปที่องค์ประกอบแรกและสุดท้ายของช่วงที่ตรงกับเงื่อนไข

ขั้นตอนการทำงาน

1. สร้างและกำหนดค่าเริ่มต้นให้เวกเตอร์
2. เรียงลำดับเวกเตอร์แบบไม่เพิ่ม (มากไปน้อย) ด้วย sort(v.begin(), v.end(), greater<int>())
3. หา Lower Bound ด้วย lower_bound() พร้อม comparator greater<int>()
4. หา Upper Bound ด้วย upper_bound() พร้อม comparator greater<int>()
5. แสดงผลดัชนี (index) ของทั้งสอง bound

สำคัญ: ต้องเรียงลำดับเวกเตอร์ก่อนจึงจะใช้ lower_bound/upper_bound ได้ถูกต้อง หากไม่เรียงลำดับจะหา bound ไม่ได้

ตัวอย่างโค้ดที่แก้ไขแล้ว (Compile ได้)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int vect[] = {13, 13, 13, 16, 16, 16, 17, 17, 17, 17, 18, 18};
    vector<int> v(vect, vect + 12);
    
    // เรียงแบบไม่เพิ่ม (มากไปน้อย)
    sort(v.begin(), v.end(), greater<int>());
    
    cout << "Sorted Vector: ";
    for (auto i : v) cout << i << " ";
    cout << endl;
    
    // ใช้ comparator greater() สำหรับ lower/upper bound
    auto low = lower_bound(v.begin(), v.end(), 17, greater<int>());
    auto up = upper_bound(v.begin(), v.end(), 17, greater<int>());
    
    cout << "Lower bound of 17 = " << (low - v.begin()) << endl;
    cout << "Upper bound of 17 = " << (up - v.begin()) << endl;
    
    return 0;
}

ผลลัพธ์

Sorted Vector: 18 18 17 17 17 17 16 16 16 13 13 13
Lower bound of 17 = 2
Upper bound of 17 = 6

ตัวอย่างที่ 2

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int vect[] = {5, 5, 5, 5, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 10, 10};
    vector<int> v(vect, vect + 16);
    
    // เรียงแบบไม่เพิ่ม
    sort(v.begin(), v.end(), greater<int>());
    
    cout << "Sorted Vector: ";
    for (auto i : v) cout << i << " ";
    cout << endl;
    
    auto low = lower_bound(v.begin(), v.end(), 8, greater<int>());
    auto up = upper_bound(v.begin(), v.end(), 8, greater<int>());
    
    cout << "Lower bound of 8 = " << (low - v.begin()) << endl;
    cout << "Upper bound of 8 = " << (up - v.begin()) << endl;
    
    return 0;
}

ผลลัพธ์

Sorted Vector: 10 10 9 9 9 8 8 8 8 7 7 7 5 5 5 5
Lower bound of 8 = 5
Upper bound of 8 = 9