def METHOD_NAME(searches: list[Search]) -> WeightedGraph:
    """Builds approximately the same graph as `build_full`, but does not
    check every possible edge.
    Time complexity: O(n*log(n))
    """
    adj_list = {search: [] for search in searches}
    # Sort all searches by players average trueskill mean
    searches = sorted(searches, key=avg_mean)
    # Now compute quality with `num_to_check` nearby searches on either side
    num_to_check = int(math.log(max(16, len(searches)), 2)) // 2
    for i, search in enumerate(searches):
        for other in searches[i + 1: i + 1 + num_to_check]:
            quality = search.quality_with(other)
            if not _MatchingGraph.is_possible_match(search, other, quality):
                continue
            # Add the edge in both directions
            adj_list[search].append((other, quality))
            adj_list[other].append((search, quality))
    # Sort edges by their weights i.e. match quality
    for search, neighbors in adj_list.items():
        neighbors.sort(key=lambda edge: edge[1])
    return adj_list