好资源导航 » 文章资讯 » 在 C++ 中的无限数排序数组中查找元素的位置

在 C++ 中的无限数排序数组中查找元素的位置

2023-06-16 12:11:02 81

在这个问题中，我们得到一个由无限排序的数字组成的数组。我们的任务是在无限数字的排序数组中查找元素的位置。

让我们举个例子来理解这个问题，

输入

arr[] = {2, 4, 6, 8, 9, 12, 14,17, ….}, ele = 9

输出结果

解释

解决方法

为了有效地从排序数组中搜索元素，我们将使用二进制搜索方法。在这里，单一的终点是未知的，我们将稍微修改一下算法。

我们将开始指针固定到第一个位置，然后将结束指针固定到第二个位置。在此之后，我们将检查结束指针处的值，如果该值小于key，则通过将其加倍来增加它，并使用结束指针的最后位置更新开始指针。

当最后一个位置值大于要查找的元素时，我们将使用二进制搜索在这个子数组中进行搜索。

程序来说明我们的解决方案的工作，

示例

#include
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<<"未找到元素！";
   else
      cout<<"Element found! index = "<输出结果Element found! index = 5

返回顶部
514930285
czq8825@qq.com

在 C++ 中的无限数排序数组中查找元素的位置

输入

解释

示例

热门推荐

随机推荐