ได้รับอาร์เรย์ของตัวเลขที่เรียงลำดับแล้วซึ่งมีเฉพาะ 0 และ 1 หาจุดเปลี่ยนผ่าน (Transition Point) จุดเปลี่ยนผ่านคือดัชนีของ '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 ตัวเลขไบนารี
- ฟังก์ชัน transitionPoint(int *arr, int n) รับอาร์เรย์เป็นอินพุตและขนาดของมัน และคืนค่าดัชนีของ '1' แรกที่ปรากฏในอาร์เรย์
- ใช้ตัวชี้สองตัว low, high ซึ่งเริ่มต้นเป็น '0' และ 'n-1'
- ตอนนี้เราจะหาจุดกลางของอาร์เรย์และจะตรวจสอบว่ามันเป็น '1' หรือไม่
- ถ้ากลางของอาร์เรย์เป็น '1' เราจะคืนค่าดัชนีของมัน มิฉะนั้นเราจะตรวจสอบโดยการเลื่อนไปข้างหน้า
- เพิ่มตัวชี้ low และตรวจสอบ '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'
