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 withfile.seek(position)to jump directly to that point.found_date(datetime.date): The date of the line atposition, orNoneif 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
Basic exact date search
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=Truegives 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; usefile.seek(offset)to jump. - Requires files in
MM/DD/YYYY,...format with no header and ascending date order.
Related
- Data completeness: context for gap-detection workflows that rely on this module.
- Data format reference: exact field layouts for every Kibot CSV product.
- Tick data: the densest format where O(log N) lookup matters most.
- Timezone conversion: the ET timestamp convention used in Kibot files.
- Continuous futures: roll-splicing uses
find_next_match=Trueto locate roll dates. - Rollover rules: the date-driven contract switches that this lookup pattern accelerates.