หา Index ของ 1 แรกใน Sorted Array ของ 0 และ 1 ใน C++

ในปัญหานี้ เราได้รับ sorted array ของ 0 และ 1 (ขนาดจำกัด) งานคือหา index ของ 1 ตัวแรก

ตัวอย่าง

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

วิธีที่ 1: Linear Search O(N)

int findFirstOneLinear(int bin[], int n) {
    for (int i = 0; i < n; i++) if (bin[i] == 1) return i;
    return -1;
}

วิธีที่ 2: Binary Search O(log N) (แนะนำ)

Standard binary search หา first occurrence ของ 1

int findFirstOneBinary(int bin[], int n) {
    int low = 0, high = n - 1;
    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 n = sizeof(bin) / sizeof(bin[0]);
    cout << findFirstOneBinary(bin, n); // 3
    return 0;
}

ผลลัพธ์

3