กำหนดอาร์เรย์ของตัวเลขที่จัดเรียงโดยมีเพียง 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 ตัวแรก เพื่อแก้ปัญหานี้ เราสามารถแก้ไขได้โดยใช้ Binary Search Method เพื่อค้นหาดัชนีของ '1' ตัวแรก
-
รับอินพุตอาร์เรย์ของ N Binary Numbers
-
ตอนนี้ฟังก์ชั่น TransitionPoint(int *arr, int n) รับอาร์เรย์เป็นอินพุตและขนาดและส่งคืนดัชนีของ '1' แรกที่ปรากฏในอาร์เรย์
-
ใช้ตัวชี้สองตัวต่ำ สูง ซึ่งเริ่มต้นเป็น '0' และ '1'
-
ตอนนี้เราจะหาจุดกึ่งกลางของอาร์เรย์และจะตรวจสอบว่าเป็น '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} มีองค์ประกอบ '1' อยู่ที่ดัชนี '3' ดังนั้นเราจึงได้ผลลัพธ์เป็น '3'
