For me it displays the concept very well. Returning func took some time to resolve the WTF, but then it became clear? What about the usage example that demonstrates the dramatic difference in search time and advocates the Func usage? Also as the usage example will be like

  var users = new List<User> { new User { Name = "Oren" }, new User { Name = "Other guy" } };             var oren = BuildIndexOnUsers(users)("Oren");

the name like "IndexUsers" or "GetIndexOnUsers" will work better IMHO.

An index usually allows you perform range searches and get results sorted, not only exact match searches. This is why I would prefer something like this

@Ayende SortedDictionary does not allow range search, only exact match.

I understand the index creation, but I must say I am not sure how the return lambda statement generates a <string, List<User>> and not List<User>, though the nested return must be doing that, somehow.

I was wondering if local function that uses yield return would be simpler (since lambda can't do that). Something like:

Func<string, IEnumerable<User>> BuildIndexOnUsers(List<User> users)
{
    var index = new Dictionary<string, List<int>>();
    for (var i = 0; i < users.Count; i++)
    {
        if (index.TryGetValue(users[i].Name, out var list) == false)
        {
            list = new List<int>();
            index[users[i].Name] = list;
        }
        list.Add(i);
    }

    IEnumerable<User> GetUsers(string username)
    {
        if (index.TryGetValue(username, out var matches))
        {
            foreach (var match in matches)
                yield return users[match];
        }
    }
    
    return GetUsers;
}

But I think your version is actually better, especially since everyone knows how creating a List works, while not everyone will know the details of yield return.

@Ayende. SortedList doesn't allow range search either. SortedDictionary and SortedList are sorted collections, but neither take advantage of its sorted nature to perform range search.

@Ayende. No. SortedList.Keys.IndexOf returns -1 if the key is not present, so, How do you search key BETWEEN from AND to if from is not in the keys?

@Ayende, but that would require a full scan, however the code I suggested doesn't.

Jesús, since the SortedList allows indexing directly into the list, you could write your own binary search for the appropriate starting key index instead of scanning the entire list.

HI, I have a question.

Lambda function returned use: users List<User> by reference as I saw. 1. does lambda code ensures it will not be GC collected after derefferenced outside?

 i.e. does
line 20 ,                ' results.Add(users[match]);'  make some kind of reference that will avoid GC ? 

Thx

@Alex, I have already wrote my own binary search over a sorted array. Did you see my code ? I don't need SortedList at all.

@Ayende, @Alex Davison. SortedSet would be a good fit. I allows you to perform ordered scan, exact match and range search, no need to implement your own binary search. Please see this code.

This might be just a little silly: ;)

var index = 0;
var lookup = users.ToLookup(user => user.Name, u => index++);
return username => lookup[username].Select(i => users[i]);

Alternatively if you want to avoid the reliance on the order of operation from the index++ interacting with the lookup code.

var lookup = users.Select((user, index) => new { user.Name, index }).ToLookup(ui => ui.Name, ui => ui.index);

Obviously the point is to then understand how ToLookup works, which I'm guessing was your real point?