在圆阵搜索 [英] Search in circular Array

问题描述

什么是一个圆阵搜索的最佳方式？

What is the best way to search in a circular array?

Example 1  array : 45 67 44 11 49 4 56 12 39 90
           circular array 11, 49, 4, 56, 12, 39, 90, 45, 67

时的二进制搜索开始与正确的方法？

Is Binary search the right approach to start with?

推荐答案

如果数组进行排序二进制搜索是唯一有用的。

Binary search is only useful if the array is sorted.

您没有提供有关该问题的领域很多信息，但一个方法是使用一组（或哈希表）。对于每次把阵的数量，也是在该组插入。一组（或哈希表）查找在固定时间内发生，所以没有搜索。当您从数组中删除一个项目，也从集合中删除。如果你的循环缓冲区覆盖值，因为它填满，确保它还会更新设置为删除覆盖值。

You didn't provide much info about the problem domain but one approach would be to use a set (or hash table). For every number you put in the array, also insert it in the set. Lookups in a set (or hash table) happen in constant time, so there's no "searching". When you remove an item from the array, also remove it from the set. If your circular buffer overwrites values as it fills up, make sure it also updates the set to remove overwritten values.

如果您无法使用另外一个数据结构，那么你可以做的最好的是阵列的线性扫描。

If you can't use another data structure, then the best you can do is a linear scan of the array.

这篇关于在圆阵搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！