数据结构
网络
关系数据库管理系统 (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 次浏览
广告