Cho một mảng các số được sắp xếp chỉ chứa các số 0 và 1, hãy tìm điểm chuyển tiếp. Điểm chuyển tiếp là chỉ số của ‘1’ đầu tiên xuất hiện trong mảng. Ví dụ:
Đầu vào-1 -
N = 6
arr[ ] = {0,0,0,0,1,1} Đầu ra -
4
Giải thích - Vì trong mảng đã cho có chứa 0 và 1 nên chúng ta có thể thấy rằng phần tử ở chỉ mục ‘4’ có số ‘1’.
Đầu vào-2 -
N = 5
arr[ ] = {0,0,1,1,1} Đầu ra -
2
Giải thích - Trong mảng đã cho có chứa 0’s và 1’s, chúng ta có thể thấy rằng phần tử ở chỉ số ‘2’ đang có số ‘1’. Do đó, chúng tôi sẽ trả về 2.
Phương pháp tiếp cận để giải quyết vấn đề này
Trong mảng số nguyên đã cho, chúng ta phải tìm chỉ số của số nguyên đầu tiên. Để giải quyết vấn đề cụ thể này, chúng ta có thể giải quyết nó bằng cách sử dụng Phương pháp tìm kiếm nhị phân để tìm chỉ số của số ‘1’ đầu tiên.
-
Lấy đầu vào một mảng N số nhị phân
-
Bây giờ một hàm chuyển tiếpPoint (int * arr, int n) nhận một mảng làm đầu vào và kích thước của nó và trả về chỉ số của ‘1’ đầu tiên xuất hiện trong mảng.
-
Lấy hai con trỏ thấp, cao được khởi tạo là ‘0’ và ‘1’.
-
Bây giờ chúng ta sẽ tìm điểm giữa của mảng và sẽ kiểm tra xem nó có phải là ‘1’ hay không.
-
Nếu phần giữa của mảng là ‘1’ thì chúng tôi sẽ trả về chỉ mục của nó, nếu không chúng tôi sẽ kiểm tra bằng cách tiếp tục.
-
Tăng con trỏ thấp lên và kiểm tra lại để tìm "1".
-
Lặp lại các bước cho đến khi chúng tôi không nhận được "1".
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int transitionPoint(int *arr, int n){
int low=0;
int high= n-1;
while(low<=high){
int mid = (low+high)/2;
if(arr[mid]==0)
low= mid+1;
else if(arr[mid]==1){
if(mid==0 || (mid>0 && arr[mid-1]==0))
return mid;
high= mid-1;
}
}
return -1;
}
int main(){
int n= 6;
int arr[n]= {0,0,0,1,1,1};
int ans= transitionPoint(arr,n);
if(ans>=0){
cout<<"Transition Point is:"<<ans<<endl;
}
else{
cout<<"Not Found"<<endl;
}
return 0;
} Đầu ra
Chạy đoạn mã trên sẽ tạo ra kết quả là,
Transition Point is: 3
Mảng đã cho {0,0,0,1,1,1} có phần tử ‘1’ hiện diện ở chỉ mục ‘3’, do đó chúng tôi nhận được kết quả là ‘3’.