在 C++ 中的无限数排序数组中查找元素的位置
在这个问题中,我们得到一个由无限排序的数字组成的数组。我们的任务是在无限数字的排序数组中查找元素的位置。
让我们举个例子来理解这个问题,
输入
arr[] = {2, 4, 6, 8, 9, 12, 14,17, ….}, ele = 9输出结果
4
解释
解决方法
为了有效地从排序数组中搜索元素,我们将使用二进制搜索方法。在这里,单一的终点是未知的,我们将稍微修改一下算法。
我们将开始指针固定到第一个位置,然后将结束指针固定到第二个位置。在此之后,我们将检查结束指针处的值,如果该值小于key,则通过将其加倍来增加它,并使用结束指针的最后位置更新开始指针。
当最后一个位置值大于要查找的元素时,我们将使用二进制搜索在这个子数组中进行搜索。
程序来说明我们的解决方案的工作,
示例
#includeusing 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