0과 1만 포함하는 정렬된 숫자 배열이 주어지면 전환점을 찾으십시오. 전환점은 배열에 나타나는 첫 번째 '1'의 인덱스입니다. 예를 들어,
입력-1 -
N = 6
arr[ ] = {0,0,0,0,1,1} 출력 -
4
설명 − 0과 1을 포함하는 주어진 배열에서 인덱스 '4'에 있는 요소가 숫자 '1'을 갖는 것을 볼 수 있습니다.
입력-2 -
N = 5
arr[ ] = {0,0,1,1,1} 출력 -
2
설명 − 0과 1을 포함하는 주어진 배열에서 인덱스 '2'에 있는 요소가 숫자 '1'을 갖고 있음을 알 수 있습니다. 따라서 2를 반환합니다.
이 문제를 해결하기 위한 접근 방식
주어진 정수 배열에서 첫 번째 1의 인덱스를 찾아야 합니다. 이 특정 문제를 해결하기 위해 이진 검색 방법을 사용하여 첫 번째 '1'의 인덱스를 찾는 문제를 해결할 수 있습니다.
-
N 이진 숫자의 배열을 입력 받아
-
이제 transitionPoint(int *arr, int n) 함수는 배열과 크기를 입력으로 받아 배열에 나타나는 첫 번째 '1'의 인덱스를 반환합니다.
-
'0'과 '1'로 초기화되는 두 개의 포인터를 low, high로 가져옵니다.
-
이제 배열의 중간 지점을 찾아 '1'인지 확인합니다.
-
배열의 중간이 '1'이면 인덱스를 반환하고 그렇지 않으면 앞으로 이동하여 확인합니다.
-
하위 포인터를 증가시키고 '1'을 다시 확인하십시오.
-
'1'이 나오지 않을 때까지 단계를 반복합니다.
예시
#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;
} 출력
위의 코드를 실행하면 출력이 다음과 같이 생성됩니다.
Transition Point is: 3
주어진 배열 {0,0,0,1,1,1}에는 인덱스 '3'에 요소 '1'이 있으므로 출력을 '3'으로 얻습니다.