ในปัญหานี้ เราได้รับ infinite array bin[] ซึ่งประกอบด้วยค่าบูลีน (เฉพาะ 0 และ 1) ในการเรียงลำดับ งานของเราคือ ค้นหาดัชนีของ 1 ตัวแรกในอาร์เรย์ที่เรียงลำดับแบบอนันต์ของ 0 และ 1 .
ที่นี่ เรามีอาร์เรย์อนันต์ซึ่งรับประกันว่ามี 1 อยู่ในอาร์เรย์
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
Input : bin[] = {0, 0, 0, 1, 1, ....}
Output : 3 คำอธิบาย −
First 1 of the binary array is encountered at index 3.
แนวทางการแก้ปัญหา
ในการแก้ปัญหานั้น โดยพื้นฐานแล้ว เราจำเป็นต้องค้นหาดัชนีที่ 1 ในอาร์เรย์ เพื่อที่เราจะสามารถใช้เทคนิคการค้นหาได้
วิธีหนึ่งสามารถใช้การค้นหาเชิงเส้นได้ เราจะสำรวจอาร์เรย์โดยใช้การวนซ้ำแบบอนันต์ และคืนค่าดัชนีของ 1 ตัวแรกในอาร์เรย์ มิฉะนั้น พิมพ์ -1
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <iostream>
using namespace std;
double find1stOneInfiniteArray(int bin[]) {
int i = 0;
while(1){
if (bin[i] == 1)
return i;
i++;
}
return -1;
}
int main() {
int bin[] = { 0, 0, 0, 1, 1, 1 };
cout<<"The index of 1st occurrence of 1 in infinite array is "<<find1stOneInfiniteArray(bin);
return 0;
} ผลลัพธ์
The index of 1st occurrence of 1 in infinite array is 3
เทคนิคการค้นหาอื่น ที่สามารถใช้ได้คือการค้นหาแบบไบนารีเมื่อจัดเรียงอาร์เรย์
เพียงแค่เราจำเป็นต้องอัปเดตอัลกอริธึมเนื่องจากไม่มีขอบเขตบนเราจะค้นหาโดยเพิ่มค่าสูงเป็นสองเท่าโดยเริ่มจากค่าดัชนี 1 ถึงดัชนีการเกิด 1 ตัวแรก
เมื่อใช้ขอบเขตเหล่านี้ เราสามารถค้นหาดัชนีโดยใช้การค้นหาแบบไบนารี
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <iostream>
using namespace std;
double find1stOneInfiniteArray(int bin[], int low, int high) {
int mid;
while (low <= high) {
mid = (low + high) / 2;
if (bin[mid] == 1 && (mid == 0 || bin[mid - 1] == 0))
return mid;
else if (bin[mid] == 1)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
int main() {
int bin[] = { 0, 0, 0, 1, 1, 1, 1 };
int low = 0;
int high = 1;
while(bin[high] != 1){
low = high;
high *= 2;
}
cout<<"The index of 1st occurrence of 1 in infinite array is " <<find1stOneInfiniteArray(bin,low, high);
return 0;
} ผลลัพธ์
The index of 1st occurrence of 1 in infinite array is 3
