在未知大小的数组上进行二进制搜索

Question

假设已经给出一个数组并且想要在该数组中找到元素，如何使用二进制搜索来搜索该数组中的元素，并且给定数组已经排序并且数组的大小未知。 线性搜索可以应用，但我想找出比线性算法更快的搜索。

Answer 1

如果可以测试是否已经下降出数组范围的，则可以使用修改后的二进制搜索（假定1-基于阵列）：

1. 低级= 1，上= 1; （A [上] <元素）upper * = 2;其中（A [上] <元素）上*
2. 正常的二进制搜索（低，高）。

否则，没有办法做到这一点：假设你找到某个地方的东西等于你需要的元素，你不知道它是否已经不在数组中。

Answer 2

这里是一个开始：

我可能会尝试这样的事情（在Java的esqe语言）。 （假设一个整数数组）

int endOfArray = 10; 
try { 
    while (true) { 
    int value = theArray[endOfArray*2]; 
    if (value > requestedValue) // good enough 
     return doBinarySearch(theArray, 0, endOfArray, requestedValue); 
    else 
     endOfArray*=2; 
    } 
} 

catch (ArrayIndexOutOfBoundsException aioob) { 
    // we know that the end of the array is less than endOfArray*2 but > endOfArray 
    // do something clever here TBD. :-) 
} 

注后补充道：如果数组是“C类”，并在最后0，你也不得不以检查。顺便说一句，如果任何人有一个简单的解决方案，“这里很聪明”的部分，请随时编辑答案。

Answer 3

以下应该工作（没有测试），但应具有相同的边界作为二进制搜索，O(log(n))：

private bool hasValue(int[] array, int search, int start, int end) 
{ 
    int mid = (start+end)/2; 

    try 
    { 
     //Check to see if we can grab the value 
     int value = array[mid]; 

     //If we are here, we are in the array 

     //Perform the binary search 
     if (value==search) 
      return true; 
     else if (end <= start) 
      return false; 
     else if (value>search) 
      return hasValue(array, search, start, mid); 
     else 
      return hasValue(array, search, mid, end*2); 

    } 
    catch(ArrayIndexOutOfBoundsException e) 
    { 
     //If we are here, then we were outside the array, so 
     //loop through the lower half 
     return hasValue(array, search, start, mid); 
    } 


} 

public bool hasValue(int[] array, int search) 
{ 
    // 0 is the start of the array (known) 
    // 1 is the end--start with any number that is greater than max(start, 1) 
    return hasValue(array, search, 0, 1); 
} 

下面是一个例子使用

// 2 is the value you are looking for 
bool hasTwo = hasValue(array, 2); 

Answer 4

假设阵列A是排序（否则你不能做二分搜索），并且你正在搜索的元素是k，你可以找到一个索引i，使得k [1]，然后从1到i（1-索引数组）。这是因为一旦确保在排序元素A [1..i]的范围内找到（或未找到）k，就保证k [k]。

要找到索引i，您应该从i = 1开始，然后在k> A [i]时加倍。这就像是二分搜索，除了你将搜索范围加倍，所以它仍然有O（log n）的运行时间。

的算法是这样的：设置I = 1，然后重复直到ķ< = A [I]：

• 如果k> A [1]，然后令i = I * 2

如果k == A [i]，那么你就完成了，否则像往常一样在A [1..i]上进行二分搜索。

Answer 5

这一个为我工作，这是O（log N + log N），即仍然O（log N）？ 这是一个有效的方式适合子阵列。 O（log N）

static int bSearch (int needle, int[] arr) 
    { 
    boolean done = false; 
    int i = 1; 
    int lower = 0; 
    int upper = 1; 
    int temp; 
    while (!done) 
    { 
     try{ 
      if (needle == arr[upper]) 
       return upper; 
      else if (needle > arr[upper]) 
      { 
       temp = lower; 
       lower = upper; 
       upper = temp + (int) Math.pow(2,i); 
       i = i + 1; 
      } 
      else 
      { 
       done = true; 
       break; //found the upper bounds 
      } 
     } 
     catch (IndexOutOfBoundsException e) 
     { 
     upper = (upper -lower)/2; 
      i = 0; 
     } 
    } 
    if (done == true) 
     //do normal binary search with bounds lower and upper and length upper-lower 
    else 
     return -1; 
    }