2

我认为二进制搜索需要顺序。我不知道我是对还是错。有什么建议吗？

4

7 回答 7

4

您需要能够在随机位置（当前部分的中间）跳跃，所以是的，需要随机访问。（另外，一个要求是集合是有序的）。也就是说，当然，前提是您的结构是列表/数组。如果是二叉树，显然不需要随机访问。

于 2012-04-10T20:24:18.683 回答
4

您可以在没有随机访问的情况下进行二进制搜索。例如，二叉树支持二进制搜索，但不支持随机访问（至少按照通常使用的术语——对集合中任何元素的恒定复杂性访问）。

元素的顺序必须允许与您正在搜索的键进行比较，以便您可以确定如果键大于某个值 X，那么它也大于所有其他小于的元素X（或者您可以使用小于而不是大于）。

虽然这种关系不必与数字排序相对应，但它确实必须能够根据仅与一个元素的比较，从考虑中排除一定百分比的元素（而不仅仅是单个元素）。

于 2012-04-10T20:24:28.560 回答
2

是的。二进制搜索必须能够以随机（非顺序）方式访问数据结构的所有元素。

于 2012-04-10T20:24:43.383 回答
2

是的，它确实需要随机访问。二分搜索的整个想法是在每次迭代时将搜索空间细分为一半，并使用索引来确定新的搜索范围。如果您每次都必须遍历搜索空间才能到达中点，那么您将否定算法的要点。

于 2012-04-10T20:25:59.637 回答
1

二分查找是“跳到中间”。因此，数据上的某种顺序是必要的（这样中间的定义很好）并且需要索引访问而不是迭代（能够跳转，否则 O(log(CollectionSize)) 的运行时间不会是可能的）。

于 2012-04-10T20:24:23.120 回答
1

它必须在搜索发生之前排序，它可以按升序或降序排序，这两种排序之间的区别在于您应该在上半部分或下半部分查找下一个位置，并根据您要查找的键确定

int binary_search(int A[], int key, int imin, int imax)
{
  // test if array is empty
  if (imax < imin):
    // set is empty, so return value showing not found
    return KEY_NOT_FOUND;
  else
    {
      // calculate midpoint to cut set in half
      int imid = (imin + imax) / 2;

      // three-way comparison
      if (A[imid] > key):
        // key is in lower subset
        return binary_search(A, key, imin, imid-1);
      else if (A[imid] < key):
        // key is in upper subset
        return binary_search(A, key, imid+1, imax);
      else:
        // key has been found
        return imid;
    }
}

如果您的数组按降序翻转二进制运算符，则此操作适用于升序

// three-way comparison
          if (A[imid] < key):
            // key is in lower subset
            return binary_search(A, key, imin, imid-1);
          else if (A[imid] > key):
            // key is in upper subset
            return binary_search(A, key, imid+1, imax);
          else:
            // key has been found
            return imid;
        }
于 2012-04-10T20:25:59.203 回答
0

值得补充的是，该Collections.binarySearch方法不需要搜索列表是 的实例，它的实现也RandomAccess将接受任何，如下所示：ListLinkedList

public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
    if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
        return Collections.indexedBinarySearch(list, key);
    else
        return Collections.iteratorBinarySearch(list, key);
}

BINARYSEARCH_THRESHOLD 等于 5000 (JDK 1.8)。当然，搜索和之前对 LinkedList 进行排序是非常低效的。此外，程序员更习惯于在数组而不是链表中考虑二进制搜索，因此Collections.binarySearch接受非 RandomAccess 集合的事实可能令人惊讶。

于 2014-03-22T19:26:43.257 回答