Binary Search packet in binary file

Question

I have binary files that consist of many 24 byte packets where the first 8 bytes in each packet represent the serialized timestamp of type DateTime. The packets are all ordered in ascending fashion by timestamp. I want to develop a binary search algorithm that picks the first 8 bytes, deserializes the timestamp, and compares it with the desired timestamp.

Goal is to find the position in the binary file that represents the starting position of the serialized timestamp that matches the desired timestamp.

Edit The data is in a binary file and not in a data structure, hence List<T>.BinarySearch() won't work for me. But might it be possible to use BinarySearch on a Stream with CustomComparer?

The file contains many dozens of millions of such packets hence a simple iteration through the file would be highly inefficient. I consider a binary search approach.

Answer 1

Haven't tested it, but the point is to read 8 bytes at in the middle of the file, than move to right or left middle and repeat, depending on read timestamp. (not the cleanest code). Complexity would be Log(N)

public class BinaryFinder
{
    private readonly long _packagesCount;
    private readonly FileStream _reader;

    public BinaryFinder(FileStream reader, int packageSize)
    {
        _reader = reader;
        _packagesCount = reader.Length / packageSize;
    }


    public long Find(DateTime dateToSearch)
    {
        return Find(0, _packagesCount, dateToSearch);
    }

    private long Find(long minPosition, long maxPosition, DateTime dateToSearch)
    {
        while (minPosition<=maxPosition) {
            var newPosition = (minPosition + maxPosition) / 2;
            var readDate = ReadDateAt(newPosition);

            if (readDate == dateToSearch) {
                return newPosition;
            }

            if (dateToSearch < readDate){
                maxPosition = newPosition-1;
            }
            else {
                minPosition = newPosition+1;
            }
        }

        return -1;
    }

    private DateTime ReadDateAt(long middlePosition)
    {
        var buffer = new byte[8];

        _reader.Seek(middlePosition, SeekOrigin.Begin);
        _reader.Read(buffer, 0, buffer.Length);

        var currentDate = ConvertBytesToDate(buffer);
        return currentDate;
    }

    private static DateTime ConvertBytesToDate(byte[] dateBytes)
    {
        throw new NotImplementedException();
    }
}

Answer 2

Ok, here is the crazy idea in code, check it, it will return the index of the structure for the timestamp you're seeking.

Just instantiate a FileStructList(fileName) and then do list.BinarySearchIndexOf(theTimeStamp);

You can even pass it your own comparer :)

This includes the binary search on the code, but as it's an IList you can use any search method available for collections.

public class FileStructList : IList<long>
{

    Stream baseStream;
    BinaryReader reader;
    int length;
    int headerSize;

    public FileStructList(string FileName, int HeaderSize)
    {
        baseStream = File.OpenRead(FileName);
        reader = new BinaryReader(baseStream);
        length = (int)((baseStream.Length - HeaderSize) / 24);
        headerSize = HeaderSize;
    }

    public long this[int index]
    {
        get
        {
            baseStream.Seek(24 * index + headerSize, SeekOrigin.Begin);
            return reader.ReadInt64();
        }

        set
        {
            throw new NotImplementedException();
        }
    }

    public int Count
    {
        get
        {
            return length;
        }
    }

    public bool IsReadOnly
    {
        get
        {
            return true;
        }
    }

    public void Add(long item)
    {
        throw new NotImplementedException();
    }

    public void Clear()
    {
        throw new NotImplementedException();
    }

    public bool Contains(long item)
    {
        return BinarySearchIndexOf(item) != -1;
    }

    public void CopyTo(long[] array, int arrayIndex)
    {
        throw new NotImplementedException();
    }

    public IEnumerator<long> GetEnumerator()
    {
        throw new NotImplementedException();
    }

    public int IndexOf(long item)
    {
        return BinarySearchIndexOf(item);
    }

    public void Insert(int index, long item)
    {
        throw new NotImplementedException();
    }

    public bool Remove(long item)
    {
        throw new NotImplementedException();
    }

    public void RemoveAt(int index)
    {
        throw new NotImplementedException();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        throw new NotImplementedException();
    }

    public Int32 BinarySearchIndexOf(long value, IComparer<long> comparer = null)
    {
        comparer = comparer ?? Comparer<long>.Default;

        Int32 lower = 0;
        Int32 upper = length - 1;

        while (lower <= upper)
        {
            Int32 middle = lower + (upper - lower) / 2;
            Int32 comparisonResult = comparer.Compare(value, this[middle]);
            if (comparisonResult == 0)
                return middle;
            else if (comparisonResult < 0)
                upper = middle - 1;
            else
                lower = middle + 1;
        }

        return -1;
    }
}