Tìm điểm chuyển đổi (transition point) trong mảng nhị phân đã sắp xếp C++

Cho mảng chỉ chứa 0 và 1, đã sắp xếp (tất cả 0 ở trước, 1 ở sau). Tìm chỉ số của **phần tử 1 đầu tiên** (điểm chuyển đổi). Ví dụ:

Đầu vào 1: {0,0,0,0,1,1} → Đầu ra: 4 (0-indexed).

Đầu vào 2: {0,0,1,1,1} → Đầu ra: 2.

Phương pháp: Tìm kiếm nhị phân (Binary Search)

• Khởi tạo low=0, high=n-1.
• Khi low <= high: tính mid.
  • Nếu arr[mid] == 0 → low = mid+1.
  • Nếu arr[mid] == 1:
    • Nếu mid==0 hoặc arr[mid-1]==0 → trả về mid (đây là 1 đầu tiên).
    • Ngược lại high = mid-1 (tìm bên trái).
• Trả về -1 nếu không tìm thấy 1.

Ví dụ mã nguồn

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

int transitionPoint(int *arr, int n) {
    int low = 0, high = n-1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == 0) low = mid + 1;
        else {
            if (mid == 0 || arr[mid-1] == 0) return mid;
            high = mid - 1;
        }
    }
    return -1;
}

int main() {
    int arr[] = {0,0,0,1,1,1};
    int n = 6;
    int ans = transitionPoint(arr, n);
    if (ans >= 0) cout << "Transition Point: " << ans;
    else cout << "Not Found";
    return 0;
}

Kết quả

Transition Point: 3

Phức tạp O(log n).