Binary Search Algorithm for Market Data Files

This article is aimed at developers who need random-access-by-date into multi-gigabyte CSV tick files. binary_search.py is a Python module that locates a specific trading date inside a large sorted CSV by performing a binary search on byte positions rather than lines. It is a single self-contained file: download binary_search.py (about 5 KB, Python 3.6+, standard library only).

Overview

Financial tick files routinely reach multiple gigabytes and contain tens of millions of lines. A naive linear scan is impractical when you need to jump to a particular trading date. The module solves this by searching byte offsets directly: it reads small windows around the midpoint of the file, locates the nearest complete line, parses the leading date field, and narrows the range in the usual binary-search fashion. Any date is found in O(log n) time regardless of file size.

The module has no external dependencies: it uses only os, datetime, and enum from the standard library.

Performance

The algorithm runs in O(log n) time complexity relative to file size. It reads only small buffers at each step rather than loading the file into memory, so RAM usage stays constant:

File Size Approximate Time
100 MB ~0.05 s
1 GB 0.1 -- 0.5 s
10 GB 0.5 -- 1.5 s

Each step reads a buffer of 500 to 2,000 bytes depending on file type. Memory consumption does not scale with file size.

Installation

Download binary_search.py, save it next to your script (or anywhere on your Python path), and import it directly. There is nothing to install:

from binary_search import find_position_in_file_binary, PositionFileType

Requirements: Python 3.6 or later (the module uses f-strings).

API reference

PositionFileType Enum

class PositionFileType(Enum):
 DAILY = 1
 INTRADAY = 2
 TICK = 3

This enum controls the buffer sizes used during the search. Choose the value that matches your file's line density:

Value Code Read Buffer Use Case
DAILY 1 500 bytes Daily OHLCV bars -- short, sparse lines
INTRADAY 2 2,000 bytes Minute/hour bars -- moderate density
TICK 3 2,000 bytes Tick-level data -- high density

The read buffer determines how many bytes are read at each binary search step to locate a complete line. If a line is longer than the buffer, the buffer is doubled and the step is repeated, so the result never depends on where a line happens to end.

find_position_in_file_binary()

def find_position_in_file_binary(
 file_name,
 date_to_find,
 file_type=PositionFileType.TICK,
 find_next_match=False,
 debug_callback=None,
 error_callback=None,
)

Parameters:

Parameter Type Default Description
file_name str (required) Absolute or relative path to the CSV data file.
date_to_find datetime.date or datetime.datetime (required) The target date to locate in the file.
file_type PositionFileType PositionFileType.TICK Controls buffer sizes. Set to match your file's data density.
find_next_match bool False When False, performs exact date match. When True, finds the first line with date >= target.
debug_callback callable or None None Optional function called with debug messages during the search. Signature: callback(message).
error_callback callable or None None Optional function called when non-fatal errors occur (e.g., decode failures on a line).

Returns a tuple:

Scenario Return Value
Date found (position, found_date, file_size)
Date not found (-1, None, file_size)
  • position (int): Byte offset from the start of the file where the first line of the target date begins. Use with file.seek(position) to jump directly to that point.
  • found_date (datetime.date): The date of the line at position, or None if not found. In lower-bound mode this can be later than the date you asked for.
  • file_size (int): Total size of the file in bytes. Useful for calculating how much data remains after the found position.

Search modes

Exact match (find_next_match=False)

The default mode. Returns the byte position of the first line matching the exact target date. If the date does not exist in the file (weekend, holiday, or simply not present), returns -1.

Typical uses: extracting all data for a specific trading date, validating that a particular date exists in a file, and jumping to a known date for inspection or repair.

Lower bound / ceiling (find_next_match=True)

Returns the byte position of the first line where the date is greater than or equal to the target. This is the more flexible mode and handles real-world scenarios where the exact date may not exist in the file.

Typical uses: finding the start of a date range when the start date might fall on a weekend or holiday (the search automatically lands on the next available trading day); building Continuous futures contracts where you need to splice data starting from a roll date that may not have tick data; and iterating through a file date-by-date without needing to know which dates have data.

Usage examples

from datetime import date
from binary_search import find_position_in_file_binary, PositionFileType

position, found_date, file_size = find_position_in_file_binary(
 file_name="ES_continuous.txt",
 date_to_find=date(2024, 3, 15),
 file_type=PositionFileType.TICK,
)

if position >= 0:
 print(f"Found {found_date} at byte offset {position:,}")
 print(f"File size: {file_size:,} bytes")
else:
 print("Date not found in file")

Finding the start position of a date range

from datetime import date
from binary_search import find_position_in_file_binary, PositionFileType

# Find the first available date on or after March 15
start_pos, start_date, _ = find_position_in_file_binary(
 file_name="ES_continuous.txt",
 date_to_find=date(2024, 3, 15),
 file_type=PositionFileType.TICK,
 find_next_match=True, # lands on next trading day if 3/15 is missing
)

# Find the first date on or after March 22 (marks the end boundary)
end_pos, end_date, file_size = find_position_in_file_binary(
 file_name="ES_continuous.txt",
 date_to_find=date(2024, 3, 22),
 file_type=PositionFileType.TICK,
 find_next_match=True,
)

if start_pos >= 0 and end_pos >= 0:
 print(f"Week of data: {start_date} to {end_date}")
 print(f"Byte range: {start_pos:,} to {end_pos:,} ({end_pos - start_pos:,} bytes)")

Using with Kibot data files

from datetime import date
from binary_search import find_position_in_file_binary, PositionFileType

# Daily data -- use DAILY file type for smaller buffers
position, found_date, _ = find_position_in_file_binary(
 file_name="ES_daily.txt",
 date_to_find=date(2024, 1, 2),
 file_type=PositionFileType.DAILY,
)

# Intraday bars
position, found_date, _ = find_position_in_file_binary(
 file_name="ES_1min.txt",
 date_to_find=date(2024, 1, 2),
 file_type=PositionFileType.INTRADAY,
)

Processing found data

from datetime import date
from binary_search import find_position_in_file_binary, PositionFileType

position, found_date, file_size = find_position_in_file_binary(
 file_name="ES_continuous.txt",
 date_to_find=date(2024, 6, 10),
 file_type=PositionFileType.TICK,
)

if position >= 0:
 with open("ES_continuous.txt", "r") as f:
 f.seek(position)
 for line in f:
 # Each line: MM/DD/YYYY,HH:MM:SS,price,volume
 fields = line.strip().split(",")
 line_date = fields[0]

 # Stop when we reach a different date
 if line_date != found_date.strftime("%m/%d/%Y"):
 break

 price = float(fields[2])
 volume = int(fields[3])
 print(f"{fields[0]} {fields[1]} price={price} vol={volume}")

How it works

The algorithm operates directly on byte positions, treating the sorted CSV as a searchable byte stream. First, it initializes low = 0 and high = file_size. Then at each step it seeks to the midpoint mid = (low + high) // 2, reads forward until it hits a newline character, and parses the first 10 characters of the resulting line as an MM/DD/YYYY date. If that date is earlier than the target the search continues in the upper half (low = mid + 1). If it is the target or later, the line is remembered as a candidate and the search continues in the lower half (high = mid - 1) in case an earlier line also qualifies. When the range is empty, the last candidate is the first line whose date is greater than or equal to the target, which is always the very beginning of that date block rather than somewhere in the middle. Exact mode returns that line only if its date equals the target; lower-bound mode returns it as is.

The file is opened in binary mode (rb) for precise byte-level seeking; only the first 10 characters of each probed line are decoded and compared as a date. This avoids the overhead and unpredictability of text-mode line buffering on large files. Edge cases (empty files, lines too short to contain a date, and decode errors) are caught and routed through the optional error callback.

Input file format

The module expects CSV files with the following characteristics: the date appears in the first field, formatted as MM/DD/YYYY (10 characters, zero-padded month and day); there is no header row (the first line of the file must be data); lines are chronologically sorted by date in ascending order (binary search requires sorted input); line terminators are \n or \r\n (both are handled); and fields are comma-separated.

Example lines (tick data):

03/15/2024,09:30:00,5200.25,150
03/15/2024,09:30:01,5200.50,75
03/15/2024,09:30:01,5200.25,200

Example lines (daily data):

03/15/2024,5198.50,5215.75,5190.00,5210.25,1845230
03/18/2024,5212.00,5225.00,5205.50,5220.75,1523440

See Data format reference for the full field layouts of every Kibot product.

Integration

The same module is used inside Kibot's own data tooling to locate date boundaries when scanning for gaps in tick data, to find roll dates when splicing individual contract files into continuous series, and to jump to specific dates for inspection and repair. Planned open-source companions are listed on the Kibot Agent page. The consistent (position, found_date, file_size) return format makes it straightforward to integrate anywhere random-access-by-date into sorted CSV files is needed.

Key Takeaways

  • O(log n) search by date in sorted CSV files; typical 10 GB file searched in 0.5-1.5 seconds.
  • Constant memory, reads a small buffer (500-2,000 bytes) at each step.
  • Zero external dependencies; Python 3.6+ standard library only. Download binary_search.py.
  • PositionFileType (DAILY/INTRADAY/TICK) tunes buffer sizes for the file's line density.
  • find_next_match=True gives lower-bound/ceiling semantics for date-range queries and roll-date logic.
  • Returns (byte_offset, date, file_size) or (-1, None, file_size) on miss; use file.seek(offset) to jump.
  • Requires files in MM/DD/YYYY,... format with no header and ascending date order.