資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中未知大小的已排序陣列中的搜尋
假設我們有一個數組，並且該陣列按升序排序，我們必須定義一個函式來在 nums 中搜索目標。如果目標存在，則返回其索引，否則返回 -1。
陣列大小未知。我們只能使用 ArrayReader 介面訪問陣列。有一個 get 函式，例如 ArrayReader.get(k)，這將返回陣列中索引 k 處的元素。
因此，如果輸入類似於陣列 = [-1,0,3,5,9,12]，目標 = 9，則輸出將為 4，因為 9 存在於 nums 中，其索引為 4
為了解決這個問題，我們將遵循以下步驟 -
high := 1，low := 0
當 reader 的 get(high) < target 時，執行 -
low := high
high = high * 2
當 low <= high 時，執行 -
mid := low + (high - low) / 2
x := reader 的 get(mid)
如果 x 與 target 相同，則 -
返回 mid
如果 x > target，則 -
high := mid - 1
否則
low := mid + 1
返回 -1
示例
讓我們看看以下實現以獲得更好的理解 -
#include <bits/stdc++.h>
using namespace std;
class ArrayReader{
private:
vector<int> v;
public:
ArrayReader(vector<int> &v){
this->v = v;
}
int get(int i){
return v[i];
}
};
class Solution {
public:
int search(ArrayReader& reader, int target) {
int high = 1;
int low = 0;
while (reader.get(high) < target) {
low = high;
high <<= 1;
}
while (low <= high) {
int mid = low + (high - low) / 2;
int x = reader.get(mid);
if (x == target)
return mid;
if (x > target) {
high = mid - 1;
}
else
low = mid + 1;
}
return -1;
}
};
main(){
Solution ob;
vector<int> v = {-1,0,3,5,9,12};
ArrayReader reader(v);
cout<<(ob.search(reader, 9));
}輸入
{-1,0,3,5,9,12}, 9輸出
4
更新於: 2020-11-17
313 次檢視
廣告