在圆形阵列中搜索

Question

在圆形阵列中搜索的最佳方式是什么？

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

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

Answer 1

二进制搜索仅在数组排序后才有用。

您没有提供有关问题域的更多信息，但一种方法是使用set（或散列表）。对于放入数组中的每个数字，也将其插入到集合中。在一个集合（或散列表）中查找时间不变，所以没有“搜索”。当您从阵列中移除一个项目时，也将其从该组中移除。如果您的循环缓冲区在填充时覆盖值，请确保它也更新该设置以删除覆盖的值。

如果您不能使用其他数据结构，那么您可以做的最好的方法就是对阵列进行线性扫描。

Answer 2

有这个相同的问题，无法看到一种方法来使用内置函数而无需运行搜索两次，所以写了一个自定义的。

可能有办法更快地完成超范围检查，但这符合我的目的。 （本来不想标准二进制搜索界面与负折射率的东西复制为消费者将其转换回真正的索引上的循环缓冲区会一直痛苦）

public bool BinarySearchCircular<T>(T[] array, T searchValue, int head, out int lowerIndex, out int upperIndex) where T : IComparable<T> 
{ 
    int bottom = 0; 
    int top = (int)array.Length - 1; 
    int count = (int)array.Length; 
    int middle = top >> 1; 
    while (top >= bottom) 
    { 
     int middleIndex = (middle + head) % count; 
     if (array[middleIndex].CompareTo(searchValue) == 0) 
     { 
      upperIndex = middleIndex; 
      lowerIndex = middleIndex; 
      return true; 
     } 
     else if (array[middleIndex].CompareTo(searchValue) > 0) 
     { 
      top = middle - 1; 
     } 
     else 
     { 
      bottom = middle + 1; 
     } 
     middle = (bottom + top) >> 1; 
    } 
    if(array[head].CompareTo(searchValue) < 0) 
    { 
    lowerIndex = head; 
    upperIndex = -1; 
    } 
    else if(array[(head+1) % count].CompareTo(searchValue) > 0) 
    { 
    upperIndex = (head+1) % count; 
    lowerIndex = -1; 
    } 
    else 
    { 
    lowerIndex = (top + head) % count; 
    upperIndex = (bottom + head) % count; 
    } 

    return false;  
}