<?php
// Members/binary_search.php

/**
 * Perform a binary search on a sorted array with duplicate support.
 *
 * @param array  $arr    A sorted array of associative arrays
 * @param mixed  $target The target value to search for
 * @param string $key    The key to compare within each array element
 * @return array         All matching results
 */
function binarySearch(array $arr, $target, string $key): array {
    $left = 0;
    $right = count($arr) - 1;
    $results = [];

    // Edge case: empty array
    if (empty($arr)) return [];

    // Check if key exists in first element
    if (!array_key_exists($key, $arr[0])) {
        trigger_error("Key '$key' not found in array elements.", E_USER_WARNING);
        return [];
    }

    // Determine if we're dealing with a numeric or string comparison
    $isNumeric = is_numeric($arr[0][$key]);
    $target = $isNumeric ? (float)$target : strtolower((string)$target);

    while ($left <= $right) {
        $mid = (int)(($left + $right) / 2);

        if (!isset($arr[$mid][$key])) {
            break; // Skip broken data
        }

        $midValue = $arr[$mid][$key];
        $midValue = $isNumeric ? (float)$midValue : strtolower((string)$midValue);

        if ($midValue == $target) {
            // Collect matching records
            $results[] = $arr[$mid];

            // Check left for more matches
            $temp = $mid - 1;
            while ($temp >= $left && isset($arr[$temp][$key])) {
                $value = $isNumeric ? (float)$arr[$temp][$key] : strtolower((string)$arr[$temp][$key]);
                if ($value === $target) {
                    array_unshift($results, $arr[$temp]);
                    $temp--;
                } else {
                    break;
                }
            }

            // Check right for more matches
            $temp = $mid + 1;
            while ($temp <= $right && isset($arr[$temp][$key])) {
                $value = $isNumeric ? (float)$arr[$temp][$key] : strtolower((string)$arr[$temp][$key]);
                if ($value === $target) {
                    $results[] = $arr[$temp];
                    $temp++;
                } else {
                    break;
                }
            }

            return $results;
        } elseif ($midValue < $target) {
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }

    return $results; // No match
}
