给定一个具有正整数和负整数的无限长排序数组。在其中找到一个元素。
编辑
数组中的所有元素都是唯一的，并且数组在正确的方向上是无限的。
有两种方法：
将索引设置在位置 100，如果要查找的元素较少，则在前 100 个项目中进行二分查找，否则将下一个索引设置在位置 200。这样，继续将索引增加 100，直到项目更大。
将索引设置为 2 的幂。首先将索引设置在位置 2，然后是 4，然后是 8，然后是 16，依此类推。再次从位置 2^K 到 2^(K + 1) 进行二分搜索，其中 item 介于两者之间。
在最好的情况下和最坏的情况下，这两种方法中的哪一种会更好？
第一种方法在元素的索引中是线性的（O(k)其中k是元素的索引）。实际上，您将需要k/100迭代才能找到大于搜索元素的元素，即O(k).
第二种方法将在同一索引中对数。O(logk). （其中k是元素的索引）。在这里，您将需要log(k)迭代，直到找到更高的元素。2^(i-1)然后，之间的二进制搜索2^i（其中i是迭代次数）也将是对数的，总计为O(logk)
因此，第二种更有效。
您可以通过小的修改或多或少地直接应用二进制搜索。这将大致对应于您的方法 2。
基本上，选择一些数字 B 并将 A 设置为 0，然后检查您要查找的元素是否在 A 和 B 之间。如果是，则在这些边界中执行通常的二分搜索，否则设置 B=A 和 A =2*A 并重复。这将花费 O(log(M))，其中 M 是您要在数组中查找的元素的位置。
如果数组是有根据的，即有一个最小元素（即你有元素x 0，x 1，...），并且所有元素都是唯一的，那么这里有一个简单的方法：如果你正在寻找数字n，您可以对索引 0, ..., n - x 0进行二分搜索。请注意，对于所有i ≥ 0，我们总是有基本的不等式x i ≥ i + x 0 。
因此，您可以在 log 2 ( n − x 0 ) 步中找到值n 。
由于数组是无限的，因此索引必然是可变长度的。这意味着对它们进行数学运算不是O(1)，这反过来意味着“首先搜索端点的二进制搜索”的时间复杂度与O(log(k)).
在搜索端点时完成的索引数学只是左移一位，这是O(log(k))因为索引向上k需要最多log(k)位并且左移一位在位数上是线性的。
在二进制搜索中完成的索引数学O(log(k))也是如此。
所以这两种算法的实际复杂度都是O(log(k)^2). 线性搜索的复杂度是O(k log k)，所以它还是会输。
只是我的2美分。我们有一个无限数组，因此让我们想象我们正在寻找非常大的数字。你想象过吗？好吧，它变得更大了。请注意，二进制搜索的间隔长度2^i = 2^(i+1)-2^i因此需要log(2^i)=i时间才能找到数字。另一方面i，达到目标间隔需要时间。所以总时间复杂度O(n)又是。我错过了什么？
这是另一种实现，它使用 2^n 来搜索元素本身的出现，然后将此子数组提供给二分搜索
e.g.
arr = 1,2,3,4,5,6,7,8,9,-1,-1,-1,-1,-1,-1...........
num = 8;
efficiency = 2logn
--完全解决方案-- 需要 O(logn) 时间复杂度
public class B {
public static void main(String[] args) {
// Assuming sorted array of infinite length
int a[] = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 };
int elementToFind = 12;
int finalIndex = getFinalIndex(a, elementToFind);
if (finalIndex == -1) {
System.out.println("Element not found");
}
System.out.println("Found element:" + a[finalIndex]);
}
private static int getFinalIndex(int[] a, int elementToFind) {
int power = 2;
int finalIndex = (int) Math.pow(2, power);
for (int i = 0; i < finalIndex;) {
if (elementToFind == a[finalIndex]) {
return finalIndex;
}
else if (elementToFind < a[finalIndex]) {
System.out.println("search through binary search algo");
// taking i as starting index in binary search call
int searchedIndex = callToBinarySearch(a, i, finalIndex);
return searchedIndex;
}
else {
i = finalIndex + 1;
power = power * 2;
finalIndex = (int) Math.pow(2, power);
}
}
return -1;
}
}
包com.population.app；
导入 java.io。; 导入 java.util。;
类演示{
public static void main(String args[]) {
int arr[] = { 1, 2, 4, 6, 8, 9, 12, 14, 17, 21, 45 };
int index = findPos(arr, 45);
if (index == -1)
System.out.println("Element not found!");
else
System.out.println("Element found! index = " + index);
}
static int findPos(int arr[], int value) {
int start = 0, end = 1;
while (arr[end] < value) {
start = end;
end = 2 * end;
// we know it is infinite but if it has finite elements it will reduce the
// overflow of legth to n-1 element other wise the code will fail has array
// index out of bound exception
if (end > arr.length) {
end = arr.length - 1;
}
}
return binarySearch(arr, start, end, value);
}
static 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;
}
}