Tìm kiếm trong mảng đã sắp xếp kích thước không xác định trong C++

Giới thiệu

Tìm target trong mảng đã sắp xếp tăng dần nhưng KHÔNG BIẾT KÍCH THƯỚC. Chỉ có thể truy cập qua interface ArrayReader.get(k). Trả về index nếu tìm thấy, -1 nếu không.

Thuật toán: Tìm kiếm nhị phân 2 giai đoạn

1. Tìm ranh giới trên (Exponential Search): Bắt đầu high = 1, nhân đôi cho đến khi get(high) >= target.
2. Binary Search trong khoảng [low, high].

Cài đặt C++

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

class ArrayReader {
    vector<int> v;
public:
    ArrayReader(vector<int>& v) : v(v) {}
    int get(int i) { return v[i]; }
};

class Solution {
public:
    int search(ArrayReader& reader, int target) {
        int low = 0, high = 1;
        // Giai đoạn 1: tìm high sao cho reader.get(high) >= target
        while (reader.get(high) < target) {
            low = high;
            high <<= 1; // high *= 2
        }
        // Giai đoạn 2: binary search
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int x = reader.get(mid);
            if (x == target) return mid;
            if (x > 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); // Output: 4
    return 0;
}

Phân tích

• Thời gian: O(log T) với T = vị trí target (giai đoạn 1) + O(log range) (giai đoạn 2) = O(log T).
• Không gian: O(1).

LeetCode 702 "Search in a Sorted Array of Unknown Size".