資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究在 C++ 中查詢無限排序陣列中元素的位置
在這個問題中，我們得到一個由無限個排序數字組成的陣列。我們的任務是在無限排序陣列中查詢元素的位置。
讓我們舉個例子來理解這個問題：
輸入
arr[] = {2, 4, 6, 8, 9, 12, 14,17, ….}, ele = 9輸出
4
解釋
解決方案方法
為了有效地從排序陣列中搜索元素，我們將使用二分查詢法。由於這裡不知道陣列的終點，我們將稍微修改一下演算法。
我們將起始指標固定在第一個位置，然後將結束指標指向第二個位置。之後，我們將檢查結束指標處的值，如果該值小於目標值，則將其加倍並更新起始指標為結束指標的最後位置。
當最後一個位置的值大於要查詢的元素時，我們將使用二分查詢在這個子陣列中進行搜尋。
程式演示了我們解決方案的工作原理：
示例
#include<iostream>
using namespace std;
int binarySearch(int arr[], int start, int end, int ele) {
if (end >= start) {
int mid = start + (end - start)/2;
if (arr[mid] == ele)
return mid;
if (arr[mid] > ele)
return binarySearch(arr, start, mid-1, ele);
return binarySearch(arr, mid+1, end, ele);
}
return -1;
}
int findPos(int arr[], int value) {
int start = 0, end = 1;
while (arr[end] < value) {
start = end;
end = 2*end;
}
return binarySearch(arr, start, end, value);
}
int main(){
int arr[] = {1, 2, 4, 6, 8, 9, 12, 14, 17, 21, 45};
int index = findPos(arr, 9);
if (index == -1)
cout<<"Element not found!";
else
cout<<"Element found! index = "<<index;
return 0;
}輸出
Element found! index = 5
更新於：2021年3月16日
354 次瀏覽
廣告