Tìm chỉ số 1 đầu tiên trong mảng vô hạn 0/1 đã sắp xếp C++

Cho mảng vô hạn bin[] chỉ chứa 0 và 1, đã sắp xếp (các 0 đứng trước, 1 đứng sau). Nhiệm vụ: tìm chỉ số của 1 đầu tiên.

Ví dụ minh họa

Input: bin[] = {0, 0, 0, 1, 1, ...} Output: 3

Phương pháp 1: Tìm kiếm tuyến tính O(index)

Duyệt từ chỉ số 0 cho đến khi gặp 1.

Phương pháp 2: Tìm kiếm nhị phân thích nghi O(log index)

Vì mảng vô hạn, không có upper bound. Tìm upper bound bằng cách nhân đôi high (1, 2, 4, 8...) cho đến khi bin[high] == 1. Sau đó binary search trong [low, high].

Ví dụ chương trình (Phương pháp 2)

#include <iostream> 
using namespace std; 

int findFirstOneInfinite(int bin[], int low, int high) {
    while (low <= high) {
        int mid = (low + high) / 2;
        if (bin[mid] == 1 && (mid == 0 || bin[mid - 1] == 0)) return mid;
        else if (bin[mid] == 1) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}

int main() {
    int bin[] = {0, 0, 0, 1, 1, 1, 1};
    int low = 0, high = 1;
    while (bin[high] != 1) { low = high; high *= 2; }
    cout << "Chỉ số 1 đầu tiên: " << findFirstOneInfinite(bin, low, high);
    return 0;
}

Kết quả

Chỉ số 1 đầu tiên: 3