# Generated from the published Markdown; run scripts/build_language_examples.py to refresh.
# Independent examples may reuse top-level names. Python remains the explanation language.


# topics/searching/binary-search.md
def binary_search(a, target):
    low, high = 0, len(a) - 1
    while low <= high:
        mid = (low + high) // 2
        if a[mid] == target:
            return mid
        if target < a[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return None

# topics/searching/binary-search.md
values = [3, 7, 11, 18, 24]
print(binary_search(values, 18))  # 3
print(binary_search(values, 3))   # 0
print(binary_search(values, 20))  # None
print(binary_search([], 18))      # None

# topics/searching/search-boundaries.md
def lower_bound(a, target):
    low, high = 0, len(a)
    while low < high:
        mid = (low + high) // 2
        if a[mid] < target:
            low = mid + 1
        else:
            high = mid
    return low

# topics/searching/search-boundaries.md
def upper_bound(a, target):
    low, high = 0, len(a)
    while low < high:
        mid = (low + high) // 2
        if a[mid] <= target:
            low = mid + 1
        else:
            high = mid
    return low

# topics/searching/bst-lookup-insertion.md
class BSTNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

# topics/searching/bst-lookup-insertion.md
def bst_search(node, target):
    while node is not None:
        if target == node.key:
            return node
        if target < node.key:
            node = node.left
        else:
            node = node.right
    return None

# topics/searching/bst-lookup-insertion.md
def bst_insert(node, key):
    if node is None:
        return BSTNode(key)
    if key < node.key:
        node.left = bst_insert(node.left, key)
    elif key > node.key:
        node.right = bst_insert(node.right, key)
    return node

root = None
for key in [50, 30, 70, 20, 40, 60, 80]:
    root = bst_insert(root, key)
root = bst_insert(root, 65)

# topics/searching/bst-traversal.md
def inorder_keys(root):
    result = []

    def visit(node):
        if node is None:
            return
        visit(node.left)
        result.append(node.key)
        visit(node.right)

    visit(root)
    return result

# topics/searching/bst-traversal.md
def preorder_keys(root):
    out = []
    def visit(node):
        if node is not None:
            out.append(node.key)
            visit(node.left)
            visit(node.right)
    visit(root)
    return out

def postorder_keys(root):
    out = []
    def visit(node):
        if node is not None:
            visit(node.left)
            visit(node.right)
            out.append(node.key)
    visit(root)
    return out

# topics/searching/bst-traversal.md
def bst_minimum(node):
    if node is None:
        return None
    while node.left is not None:
        node = node.left
    return node

# topics/searching/bst-traversal.md
def bst_maximum(node):
    if node is None:
        return None
    while node.right is not None:
        node = node.right
    return node

def bst_successor(root, key):
    candidate = None
    node = root
    while node is not None:
        if key < node.key:
            candidate = node
            node = node.left
        else:
            node = node.right
    return candidate

def bst_predecessor(root, key):
    candidate = None
    node = root
    while node is not None:
        if node.key < key:
            candidate = node
            node = node.right
        else:
            node = node.left
    return candidate

# topics/searching/bst-range-queries.md
def bst_range_keys(root, low, high):
    if low > high:
        raise ValueError("lower bound exceeds upper bound")
    out = []

    def visit(node):
        if node is None:
            return
        if low < node.key:
            visit(node.left)
        if low <= node.key <= high:
            out.append(node.key)
        if node.key < high:
            visit(node.right)

    visit(root)
    return out

# topics/searching/bst-deletion.md
def bst_delete(node, key):
    if node is None:
        return None
    if key < node.key:
        node.left = bst_delete(node.left, key)
    elif key > node.key:
        node.right = bst_delete(node.right, key)
    else:
        if node.left is None:
            return node.right
        if node.right is None:
            return node.left
        successor = bst_minimum(node.right)
        node.key = successor.key
        node.right = bst_delete(node.right, successor.key)
    return node

# topics/searching/ordered-set-operations.md
class OrderedSet:
    def __init__(self, insert_key, delete_key):
        self._root = None
        self._size = 0
        self._insert_key = insert_key
        self._delete_key = delete_key

    def __len__(self):
        return self._size

    def size(self):
        return len(self)

    def is_empty(self):
        return len(self) == 0

    def contains(self, key):
        return bst_search(self._root, key) is not None

    def add(self, key):
        if not self.contains(key):
            self._root = self._insert_key(self._root, key)
            self._size += 1

    def remove(self, key):
        if not self.contains(key):
            raise KeyError(key)
        self._root = self._delete_key(self._root, key)
        self._size -= 1

    def discard(self, key):
        if self.contains(key):
            self.remove(key)

    def _required_key(self, node):
        if node is None:
            raise KeyError("no key satisfies the query")
        return node.key

    def minimum(self):
        return self._required_key(bst_minimum(self._root))

    def maximum(self):
        return self._required_key(bst_maximum(self._root))

    def successor(self, key):
        return self._required_key(bst_successor(self._root, key))

    def predecessor(self, key):
        return self._required_key(bst_predecessor(self._root, key))

    def extract_min(self):
        key = self.minimum()
        self.remove(key)
        return key

    def extract_max(self):
        key = self.maximum()
        self.remove(key)
        return key

    def keys(self):
        return inorder_keys(self._root)

    def range_keys(self, low, high):
        return bst_range_keys(self._root, low, high)