Search in circular Array

Question

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?

Choong

binary search requires that the data is already ordered... – Pettifogging

and how do you define 'best'? – Pettifogging

A circular array is basically a size-limited linear array so how would you sort in-place with a linear array? As @MitchWheat mentioned, defining best way is needed. – Blastula

Answer 1

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.

Jehiah

Answer 2

Had this same problem, couldn't see a way to use builtin functions without running the search twice so wrote a custom one.

There is probably a way to do the out of range check quicker, but this serves my purpose. (Didn't want to copy the standard binary search interface with the negative index stuff as the consumer converting it back to real indexes on a circular buffer would have been painful)

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

Extend