Search in a Sorted Array of Unknown Size – ค้นหาในอาร์เรย์ขนาดไม่รู้จัก C++

ปัญหา: Search in a Sorted Array of Unknown Size

อาร์เรย์เรียงเพิ่มขึ้น แต่ ขนาดไม่ทราบ เข้าถึงได้เฉพาะผ่าน ArrayReader.get(k)
หา index ของ target ไม่เจอ → -1

ตัวอย่าง

Array: [-1,0,3,5,9,12], target = 9 → Output: 4

แนวทางแก้ปัญหา: Exponential Search + Binary Search

ขั้นตอน

1. Exponential Search (หาขอบเขต):
   • เริ่ม low = 0, high = 1
   • ขยาย high ×2 จนกว่า reader.get(high) >= target (หรือ out of bounds → คืนค่ามากกว่า target)
2. Binary Search ในช่วง [low, high]:
   • มาตรฐาน binary search
   • ใช้ reader.get(mid) แทนการเข้าถึงอาร์เรย์โดยตรง

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

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

class ArrayReader {
    vector<int> v;
public:
    ArrayReader(vector<int>& v) : v(v) {}
    int get(int i) {
        if (i >= v.size()) return INT_MAX; // simulate out of bounds
        return v[i];
    }
};

class Solution {
public:
    int search(ArrayReader& reader, int target) {
        int low = 0, high = 1;

        // Exponential search for upper bound
        while (reader.get(high) < target) {
            low = high;
            high <<= 1; // high *= 2
        }

        // Binary search
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int val = reader.get(mid);
            if (val == target) return mid;
            if (val > target) high = mid - 1;
            else low = mid + 1;
        }
        return -1;
    }
};

int main() {
    vector<int> v = {-1, 0, 3, 5, 9, 12};
    ArrayReader reader(v);
    Solution ob;
    cout << ob.search(reader, 9); // 4
    return 0;
}

ความซับซ้อน

• เวลา: O(log T) โดย T = index ของ target (Exponential: log T, Binary: log T)
• พื้นที่: O(1)

ข้อสังเกต

• LeetCode 702
• ArrayReader.get อาจคืนค่าพิเศษ (เช่น INT_MAX) เมื่อ index เกินขอบเขต – ต้องจัดการ
• Exponential search เรียกว่า "Galloping search" หรือ "Doubling search"
• ใช้ได้กับ infinite stream / ไฟล์ขนาดใหญ่ที่ไม่รู้ขนาด