二进制搜索未知大小的数组-Java 学习之路

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

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;
    }

回复于 2024-04-27T09:27:55+08:00

0
假设数组A已排序（否则您无法进行二分查找），并且您要搜索的元素为k，您可以找到索引i，使得k <A [i]，然后从1进行二进制搜索到i（1索引数组） . 这是因为一旦k <A [i]，就保证在排序元素A [1..i]的范围内找到（或未找到）k .

要找到索引i，您将从i = 1开始，然后在k> A [i]时加倍 . 这就像二进制搜索，除了你的搜索范围加倍，因此它仍然有一个O（log n）运行时间 .

该算法类似于：设置i = 1，然后重复直到k <= A [i]：
- 如果k> A [i]则让i = i * 2
如果k == A [i]，那么你就完成了，否则就像往常一样在A [1..i]上进行二分搜索 .
回复于 2024-04-27T09:27:55+08:00

以下应该工作（尚未测试），但应该具有与二进制搜索相同的边界， 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);

回复于 2024-04-27T09:27:55+08:00

1
如果您可以测试是否已超出数组范围，则可以使用修改后的二进制搜索（假设基于1的数组）：
- lower = 1，upper = 1;
- while（A [upper] <element）upper * = 2;
- 正常二进制搜索（下，上） .
否则，没有真正的方法可以做到这一点：假设你发现某个地方等于你需要的元素，你不知道它是否已经脱离了数组 .
回复于 2024-04-27T09:27:55+08:00

这是一个开始：

我可能会尝试这样的东西（用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-like”并且最后有0，那么您还必须检查它 . 顺便说一句，如果有人对“聪明的东西”部分有一个简单的解决方案，请随时编辑答案 .

回复于 2024-04-27T09:27:55+08:00

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

5 回答

相关问题