Search Example — search_sorted_real, search_sorted_integer¶
This example generates a sorted array of 1000 random integers and searches
for specific values using utilities.search_sorted_real() and
utilities.search_sorted_integer(). It then benchmarks search time
across array sizes from 100 to 100 000 elements and plots a bar-chart and
log-scale comparison using utilities.cpu_time() for timing.
Example Code¶
"""IMSL search example: binary search with search_sorted_real and search_sorted_integer.
Outputs:
- Search results printed to stdout
- SVG bar chart of search times vs array size saved to
test_output/example_imsl_search.svg
"""
from __future__ import annotations
from pathlib import Path
from typing import Dict
import matplotlib.pyplot as plt
import numpy as np
from utilities import (
sort_real,
sort_integer,
search_sorted_real,
search_sorted_integer,
cpu_time,
)
def run_demo_imsl_search() -> Dict[str, object]:
"""Demonstrate binary search on sorted real and integer arrays.
Generates a sorted array of 1000 random integers, searches for specific
values using :func:`utilities.search_sorted_real` and
:func:`utilities.search_sorted_integer`, then benchmarks search time across
several array sizes to compare performance scaling.
Args:
None
Returns:
Dict[str, object]: Result dict with keys ``target_real`` (float),
``idx_real`` (int), ``target_int`` (int), ``idx_int`` (int),
``sizes`` (list[int]), ``times_real`` (list[float]),
``times_int`` (list[float]), and ``plot_path`` (str).
"""
rng = np.random.default_rng(42)
# ── 1. Basic search demonstration on 1000-element arrays ─────────────────
raw_int = rng.integers(0, 5000, size=1000).astype(int)
arr_int = sort_integer(np.array(raw_int))
arr_real = sort_real(arr_int.astype(float))
target_real = 2500.0
target_int = 2500
idx_real = search_sorted_real(arr_real, target_real)
idx_int = search_sorted_integer(arr_int, target_int)
print("\nIMSL Search Example")
print("=" * 60)
print("Array: 1000 sorted integers in range [0, 5000)")
print()
print(f" search_sorted_real (target={target_real:.0f}): index={idx_real:>4d},"
f" value at idx={arr_real[idx_real]:.0f}")
print(f" search_sorted_integer (target={target_int} ): index={idx_int:>4d},"
f" value at idx={arr_int[idx_int]}")
print()
# Show a few more lookups
lookups = [0.0, 1000.0, 2500.0, 4000.0, 4999.0]
print(f" {'Target':>8} {'idx':>6} {'arr[idx]':>10} {'arr[idx+1]':>12}")
print(" " + "-" * 44)
for tgt in lookups:
i = search_sorted_real(arr_real, tgt)
lo = f"{arr_real[i]:.0f}"
hi = f"{arr_real[i + 1]:.0f}" if i + 1 < len(arr_real) else "—"
print(f" {tgt:>8.0f} {i:>6d} {lo:>10} {hi:>12}")
# ── 2. Benchmark: search time vs array size ───────────────────────────────
sizes = [100, 500, 1_000, 5_000, 10_000, 50_000, 100_000]
repeats = 2000
times_real: list[float] = []
times_int: list[float] = []
print()
print(f" {'Size':>8} {'Real (µs)':>12} {'Int (µs)':>12}")
print(" " + "-" * 36)
for sz in sizes:
data_int = np.sort(rng.integers(0, sz * 5, size=sz).astype(int))
data_real = data_int.astype(float)
mid_real = float(data_real[sz // 2])
mid_int = int(data_int[sz // 2])
t0 = cpu_time()
for _ in range(repeats):
search_sorted_real(data_real, mid_real)
t_real = (cpu_time() - t0) / repeats * 1e6
t0 = cpu_time()
for _ in range(repeats):
search_sorted_integer(data_int, mid_int)
t_int = (cpu_time() - t0) / repeats * 1e6
times_real.append(t_real)
times_int.append(t_int)
print(f" {sz:>8d} {t_real:>12.4f} {t_int:>12.4f}")
# ── 3. Plot ───────────────────────────────────────────────────────────────
output_dir = Path("test_output")
output_dir.mkdir(parents=True, exist_ok=True)
plot_path = output_dir / "example_imsl_search.svg"
x = np.arange(len(sizes))
width = 0.35
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(13, 5))
ax1.bar(x - width / 2, times_real, width, label="search_sorted_real",
color="#b45309", alpha=0.85)
ax1.bar(x + width / 2, times_int, width, label="search_sorted_integer",
color="#d97706", alpha=0.85)
ax1.set_xticks(x)
ax1.set_xticklabels([str(s) for s in sizes], rotation=30, ha="right")
ax1.set_xlabel("Array size")
ax1.set_ylabel("Mean search time (µs)")
ax1.set_title("Search time vs array size")
ax1.legend()
ax1.grid(True, alpha=0.3, axis="y")
ax2.plot(sizes, times_real, "o-", color="#b45309", label="Real", linewidth=2)
ax2.plot(sizes, times_int, "s-", color="#d97706", label="Integer", linewidth=2)
ax2.set_xscale("log")
ax2.set_xlabel("Array size (log scale)")
ax2.set_ylabel("Mean search time (µs)")
ax2.set_title("Search time scaling (log x-axis)")
ax2.legend()
ax2.grid(True, alpha=0.3)
fig.suptitle("IMSL Search: search_sorted_real / search_sorted_integer",
fontweight="bold")
fig.tight_layout()
fig.savefig(plot_path, format="svg")
plt.close(fig)
print(f"\nPlot saved to: {plot_path}")
return {
"target_real": target_real,
"idx_real": idx_real,
"target_int": target_int,
"idx_int": idx_int,
"sizes": sizes,
"times_real": times_real,
"times_int": times_int,
"plot_path": str(plot_path),
}
if __name__ == "__main__":
run_demo_imsl_search()
Plot Output¶
Left: mean search time (µs) per array size for real and integer arrays. Right: same data on a log x-axis showing near-constant scaling.¶
Console Output¶
IMSL Search Example
============================================================
Array: 1000 sorted integers in range [0, 5000)
search_sorted_real (target=2500): index= 490, value at idx=2496
search_sorted_integer (target=2500 ): index= 490, value at idx=2496
Target idx arr[idx] arr[idx+1]
--------------------------------------------
0 -1 4995 21
1000 212 999 1007
2500 490 2496 2501
4000 803 3996 4003
4999 999 4995 ΓÇö
Size Real (┬╡s) Int (┬╡s)
------------------------------------
100 7.8125 0.0000
500 0.0000 0.0000
1000 0.0000 7.8125
5000 0.0000 0.0000
10000 7.8125 0.0000
50000 0.0000 0.0000
100000 7.8125 0.0000
Plot saved to: test_output\example_imsl_search.svg