Cho một dãy số khoảng 1000000 kí tự số toàn 0 và 1. Biết rằng các số 0 đứng trước các chữ số 1: 000....0011...11. Hãy cho biết vị trí của số 0 cuối cùng trong dãy. Thuật toán: Ta tiến hành tìm kiếm nhị phân trên xâu kí tự để tìm ra vị trí số 0 cuối cùng như sau: - Tìm phần tử giữa xâu đang xét - So sánh kí tự ở vị trí giữa xâu với kí tự 0. - Nếu kí tự giữa xâu là kí tự 0 thì ta tìm ở nửa sau của xâu, nếu không phải kí tự 0 (mà là 1) thì ta tìm ở nửa trước của xâu. //giúp mình nha !! yhamks
1 câu trả lời
#include<bits/stdc++.h>
using namespace std;
void nhap(int a[],int n) {
for(int i=0;i<n;i++)
{
cin>>a[i];
}
}
void xuly(int a[],int d,int c) {
int mid;
while(d<=c)
{
mid=(d+c)/2;
if(a[mid]==0)
d = mid + 1;
else c = mid - 1;
}
cout<<mid-1;
}
int main()
{
int n,a[100];
cin>>n;
nhap(a,n);
xuly(a,0,n-1);
return 0;
}
