Cho mảng bin[] kích thước n chỉ chứa 0 và 1, đã sắp xếp. 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(n)
Duyệt từ 0 đến n-1, trả về chỉ số đầu tiên có giá trị 1.
Phương pháp 2: Tìm kiếm nhị phân O(log n)
Binary search chuẩn, kiểm tra mid == 1 và (mid == 0 || bin[mid-1] == 0).
Ví dụ chương trình (Phương pháp 2)
#include <iostream>
using namespace std;
int findFirstOne(int bin[], int n) {
int low = 0, high = n - 1, mid;
while (low <= high) {
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 << "Chỉ số 1 đầu tiên: " << findFirstOne(bin, n);
return 0;
}
Kết quả
Chỉ số 1 đầu tiên: 3