โปรแกรมตรวจสอบอาร์เรย์ Bitonic (บิทอนิก) ใน C++

Bitonic Array คืออะไร?

Bitonic Array คืออาร์เรย์ที่มีลำดับค่า เพิ่มขึ้นอย่างเคร่งครัด (strictly increasing) ก่อน แล้วตามด้วยลำดับค่า ลดลงอย่างเคร่งครัด (strictly decreasing)

รูปแบบ: a[0] < a[1] < ... < a[peak] > a[peak+1] > ... > a[n-1]

ตัวอย่าง

ขั้นตอนการตรวจสอบ

1. เดินจากซ้ายไปขวา หาจุดที่หยุดเพิ่ม (peak)
2. ถ้าไม่มีการเพิ่มเลย (peak อยู่ตำแหน่งแรก) → ไม่ใช่ Bitonic
3. ถ้าเพิ่มจนจบอาร์เรย์ (peak อยู่ตำแหน่งสุดท้าย) → ไม่ใช่ Bitonic
4. จาก peak เดินต่อไปขวา ตรวจสอบว่าลดลงอย่างเคร่งครัดจนจบอาร์เรย์
5. ถ้าผ่านเงื่อนไขทั้งหมด → เป็น Bitonic Array

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

bool isBitonic(int arr[], int size) {
    if (size < 3) return false;  // ต้องมีอย่างน้อย 3 องค์ประกอบ
    
    int i = 1;
    
    // หาส่วนที่เพิ่มขึ้น (strictly increasing)
    while (i < size && arr[i] > arr[i - 1]) {
        i++;
    }
    
    // ตรวจสอบ peak: ไม่ใช่ตัวแรก ไม่ใช่ตัวสุดท้าย
    if (i == 1 || i == size) return false;
    
    // หาส่วนที่ลดลง (strictly decreasing)
    while (i < size && arr[i] < arr[i - 1]) {
        i++;
    }
    
    // ถ้าเดินจบอาร์เรย์ → เป็น Bitonic
    return (i == size);
}

int main() {
    int testCases[][7] = {
        {1, 3, 5, 4, 2, 0},
        {-3, 9, 11, 20, 17, 5, 1},
        {1, 2, 3, 4, 5, 0, -1, -2, 6, -4},
        {1, 2, 3, 4, 5},
        {5, 4, 3, 2, 1}
    };
    int sizes[] = {6, 7, 10, 5, 5};
    
    for (int t = 0; t < 5; t++) {
        cout << "Array: ";
        for (int i = 0; i < sizes[t]; i++) cout << testCases[t][i] << " ";
        cout << "→ " << (isBitonic(testCases[t], sizes[t]) ? "Bitonic" : "Not Bitonic") << endl;
    }
    return 0;
}

ผลลัพธ์ตัวอย่าง

Array: 1 3 5 4 2 0 → Bitonic
Array: -3 9 11 20 17 5 1 → Bitonic
Array: 1 2 3 4 5 0 -1 -2 6 -4 → Not Bitonic
Array: 1 2 3 4 5 → Not Bitonic
Array: 5 4 3 2 1 → Not Bitonic

ความซับซ้อนของอัลกอริทึม

• เวลา: O(n) - เดินผ่านอาร์เรย์เพียงครั้งเดียว
• พื้นที่: O(1) - ใช้ตัวแปรช่วยเพียงไม่กี่ตัว

การประยุกต์ใช้

• การค้นหาค่าสูงสุดใน Bitonic Array (ใช้ Binary Search ได้ใน O(log n))
• การจัดเรียง Bitonic Sort (อัลกอริทึมจัดเรียงแบบขนาน)
• การประมวลผลสัญญาณและการวิเคราะห์ข้อมูล