数据结构
网络
关系数据库管理系统
操作系统
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 次查看
广告