Skip to content

Binary Search

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import sys
import functools

def trace_vars(*varnames):
    def decorator(func):
        @functools.wraps(func)
        def wrapper(*args, **kwargs):
            steps = []
            last_snapshot = None

            def tracer(frame, event, arg):
                nonlocal last_snapshot

                if frame.f_code == func.__code__ and event == "line":

                    # only record if all variables exist
                    if not all(name in frame.f_locals for name in varnames):
                        return tracer

                    snapshot = {name: frame.f_locals[name] for name in varnames}

                    if snapshot != last_snapshot:
                        steps.append(snapshot.copy())
                        last_snapshot = snapshot

                return tracer

            sys.settrace(tracer)
            result = func(*args, **kwargs)
            sys.settrace(None)

            return result, steps

        return wrapper
    return decorator


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from typing import List
import pandas as pd
from IPython.display import display

def search(nums: List[int], target: int) -> int:
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        value = nums[mid]
        if value == target:
            return mid
        elif value < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1



checks = [([-1,0,3,5,9,12], 9, 4),([-1,0,3,5,9,12], 2, -1)]
for nums, target, expected in checks:
    traced_search = trace_vars("left", "mid", "right", "value", "target")(search)
    result, steps = traced_search(nums, target)
    display(pd.DataFrame(steps))
    assert result == expected