資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究在 C++ 中查詢無限排序的 0 和 1 陣列中第一個 1 的索引
在這個問題中，我們得到一個無限陣列 bin[]，它包含按排序順序排列的布林值（只有 0 和 1）。我們的任務是查詢無限排序的 0 和 1 陣列中第一個 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
另一種可以使用的搜尋技術是二分查詢，因為陣列已排序。
我們只需要更新演算法，因為沒有上限，我們將透過將 high 的值從索引值 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
更新於： 2022-01-28
477 次瀏覽
廣告