在無數排序數組中查找元素的位置 · GeeksForGeeks 中文系列教程

# 在無數排序數組中查找元素的位置 > 原文： [https://www.geeksforgeeks.org/find-position-element-sorted-array-infinite-numbers/](https://www.geeksforgeeks.org/find-position-element-sorted-array-infinite-numbers/) 假設您有一個無窮個排序數組，那么如何搜索數組中的元素？資料來源：Amazon Interview Experience。由于數組已排序，因此首先想到的是二分搜索，但是這里的問題是我們不知道數組的大小。如果數組是無限的，則意味著我們沒有適當的界限來應用二分搜索。因此，為了找到鍵的位置，我們首先找到邊界，然后應用二分搜索算法。讓 low 指向數組的第一個元素，high 指向數組的第二個元素，現在將鍵與高索引元素進行比較，如果 ->大于高索引元素，則將高索引復制到低索引中并將高兩倍指數。 ->如果較小，則對找到的高低索引進行二分搜索。以下是上述算法的實現 ## C++ ```cpp // C++ program to demonstrate working of an algorithm that finds // an element in an array of infinite size #include<bits/stdc++.h> using namespace std; // Simple binary search algorithm int binarySearch(int arr[], int l, int r, int x) { ????if (r>=l) ????{ ????????int mid = l + (r - l)/2; ????????if (arr[mid] == x) ????????????return mid; ????????if (arr[mid] > x) ????????????return binarySearch(arr, l, mid-1, x); ????????return binarySearch(arr, mid+1, r, x); ????} ????return -1; } // function takes an infinite size array and a key to be //? searched and returns its position if found else -1\. // We don't know size of arr[] and we can assume size to be // infinite in this function. // NOTE THAT THIS FUNCTION ASSUMES arr[] TO BE OF INFINITE SIZE // THEREFORE, THERE IS NO INDEX OUT OF BOUND CHECKING int findPos(int arr[], int key) { ????int l = 0, h = 1; ????int val = arr[0]; ????// Find h to do binary search ????while (val < key) ????{ ????????l = h;??????? // store previous high ????????h = 2*h;????? // double high index ????????val = arr[h]; // update new val ????} ????// at this point we have updated low and ????// high indices, Thus use binary search? ????// between them ????return binarySearch(arr, l, h, key); } // Driver program int main() { ????int arr[] = {3, 5, 7, 9, 10, 90, 100, 130,? ???????????????????????????????140, 160, 170}; ????int ans = findPos(arr, 10); ????if (ans==-1) ????????cout << "Element not found"; ????else ????????cout << "Element found at index " << ans; ????return 0; } ``` ## Java ```java // Java program to demonstrate working of? // an algorithm that finds an element in an? // array of infinite size class Test { ????// Simple binary search algorithm ????static int binarySearch(int arr[], int l, int r, int x) ????{ ????????if (r>=l) ????????{ ????????????int mid = l + (r - l)/2; ????????????if (arr[mid] == x) ????????????????return mid; ????????????if (arr[mid] > x) ????????????????return binarySearch(arr, l, mid-1, x); ????????????return binarySearch(arr, mid+1, r, x); ????????} ????????return -1; ????} ????// Method takes an infinite size array and a key to be ????// searched and returns its position if found else -1\. ????// We don't know size of arr[] and we can assume size to be ????// infinite in this function. ????// NOTE THAT THIS FUNCTION ASSUMES arr[] TO BE OF INFINITE SIZE ????// THEREFORE, THERE IS NO INDEX OUT OF BOUND CHECKING ????static int findPos(int arr[],int key)? ????{ ????????int l = 0, h = 1; ????????int val = arr[0]; ????????// Find h to do binary search ????????while (val < key) ????????{ ????????????l = h;???? // store previous high ????????????//check that 2*h doesn't exceeds array? ????????????//length to prevent ArrayOutOfBoundException ????????????if(2*h < arr.length-1) ???????????????h = 2*h;????????????? ????????????else ???????????????h = arr.length-1; ????????????val = arr[h]; // update new val ????????} ????????// at this point we have updated low ????????// and high indices, thus use binary? ????????// search between them ????????return binarySearch(arr, l, h, key); ????} ????// Driver method to test the above function ????public static void main(String[] args)? ????{ ????????int arr[] = new int[]{3, 5, 7, 9, 10, 90,? ????????????????????????????100, 130, 140, 160, 170}; ????????int ans = findPos(arr,10); ????????if (ans==-1) ????????????System.out.println("Element not found"); ????????else ????????????System.out.println("Element found at index " + ans); ????} } ``` ## Python ``` # Python Program to demonstrate working of an algorithm that finds # an element in an array of infinite size # Binary search algorithm implementation def binary_search(arr,l,r,x): ????if r >= l: ????????mid = l+(r-l)/2 ????????if arr[mid] == x: ????????????return mid ????????if arr[mid] > x: ????????????return binary_search(arr,l,mid-1,x) ????????return binary_search(arr,mid+1,r,x) ????return -1 # function takes an infinite size array and a key to be # searched and returns its position if found else -1\. # We don't know size of a[] and we can assume size to be # infinite in this function. # NOTE THAT THIS FUNCTION ASSUMES a[] TO BE OF INFINITE SIZE # THEREFORE, THERE IS NO INDEX OUT OF BOUND CHECKING def findPos(a, key): ????l, h, val = 0, 1, arr[0] ????# Find h to do binary search ????while val < key: ????????l = h??????????? #store previous high ????????h = 2*h????????? #double high index ????????val = arr[h]?????? #update new val ????# at this point we have updated low and high indices, ????# thus use binary search between them ????return binary_search(a, l, h, key) # Driver function arr = [3, 5, 7, 9, 10, 90, 100, 130, 140, 160, 170] ans = findPos(arr,10) if ans == -1: ????print "Element not found" else: ????print"Element found at index",ans # This code is contributed by __Devesh Agrawal__ ``` ## C# ```cs // C# program to demonstrate working of an? // algorithm that finds an element in an // array of infinite size using System; class GFG { ????// Simple binary search algorithm ????static int binarySearch(int []arr, int l, ????????????????????????????????int r, int x) ????{ ????????if (r >= l) ????????{ ????????????int mid = l + (r - l)/2; ????????????if (arr[mid] == x) ????????????????return mid; ????????????if (arr[mid] > x) ????????????????return binarySearch(arr, l,? ???????????????????????????????????mid-1, x); ????????????return binarySearch(arr, mid+1, ???????????????????????????????????????r, x); ????????} ????????return -1; ????} ????// Method takes an infinite size array ????// and a key to be searched and returns ????// its position if found else -1\. We ????// don't know size of arr[] and we can ????// assume size to be infinite in this? ????// function. ????// NOTE THAT THIS FUNCTION ASSUMES? ????// arr[] TO BE OF INFINITE SIZE ????// THEREFORE, THERE IS NO INDEX OUT? ????// OF BOUND CHECKING ????static int findPos(int []arr,int key)? ????{ ????????int l = 0, h = 1; ????????int val = arr[0]; ????????// Find h to do binary search ????????while (val < key) ????????{ ????????????l = h;???? // store previous high ????????????h = 2 * h;// double high index ????????????val = arr[h]; // update new val ????????} ????????// at this point we have updated low ????????// and high indices, thus use binary? ????????// search between them ????????return binarySearch(arr, l, h, key); ????} ????// Driver method to test the above ????// function ????public static void Main()? ????{ ????????int []arr = new int[]{3, 5, 7, 9, ????????????10, 90, 100, 130, 140, 160, 170}; ????????int ans = findPos(arr, 10); ????????if (ans == -1) ????????????Console.Write("Element not found"); ????????else ????????????Console.Write("Element found at " ????????????????????????????+ "index " + ans); ????} } // This code is contributed by nitin mittal. ``` ## PHP ```php <?php // PHP program to demonstrate working // of an algorithm that finds an? // element in an array of infinite size // Simple binary search algorithm function binarySearch($arr, $l,? ??????????????????????$r, $x) { ????if ($r >= $l) ????{ ????????$mid = $l + ($r - $l)/2; ????????if ($arr[$mid] == $x) ????????????return $mid; ????????if ($arr[$mid] > $x) ????????????return binarySearch($arr, $l,? ???????????????????????????$mid - 1, $x); ????????return binarySearch($arr, $mid + 1, ???????????????????????????????????$r, $x); ????} ????return -1; } // function takes an infinite // size array and a key to be // searched and returns its? // position if found else -1\. // We don't know size of arr[]? // and we can assume size to be // infinite in this function. // NOTE THAT THIS FUNCTION ASSUMES // arr[] TO BE OF INFINITE SIZE // THEREFORE, THERE IS NO INDEX? // OUT OF BOUND CHECKING function findPos( $arr, $key) { ????$l = 0; $h = 1; ????$val = $arr[0]; ????// Find h to do binary search ????while ($val < $key) ????{ ????????// store previous high ????????$l = $h;????? ?????????// double high index ????????$h = 2 * $h; ????????// update new val ????????$val = $arr[$h];? ????} ????// at this point we have ????// updated low and high? ????// indices, Thus use binary ????// search between them ????return binarySearch($arr, $l,? ????????????????????????$h, $key); } ????// Driver Code ????$arr = array(3, 5, 7, 9, 10, 90, 100, ?????????????????130, 140, 160, 170); ????$ans = findPos($arr, 10); ????if ($ans==-1) ????????echo "Element not found"; ????else ????????echo "Element found at index " , $ans; // This code is contributed by anuj_67\. ?> ``` 輸出： ``` Element found at index 4 ``` 令 p 為要搜索元素的位置。查找高索引“ h”的步驟數為 O（Log p）。 “ h”的值必須小于 2 * p。 h / 2 和 h 之間的元素數必須為 O（p）。因此，二分搜索步驟的時間復雜度也為 O（Log p），總時間復雜度為 2 * O（Log p），即 O（Log p）。