String.IndexOf search algorithm

This is not a full answer, but:

String.IndexOf(String) calls CultureInfo.CurrentCulture.CompareInfo.IndexOf, which calls (at least in some of the cases) CompareInfo.SyntheticIndexOf, which, in decompiled pseudo-code, looks like this:

private int SyntheticIndexOf(string source, string value, int start, int length, int nativeCompareFlags)

{

      if (CompareInfo.fFindNLSStringSupported >= 0)

      {

            int num1 = CompareInfo.FindNLSStringWrap(this.m_sortingLCID, nativeCompareFlags | 0x400000, source, start, length, value, value.Length);

            if (num1 >= -1)

            {

                  return num1;

            }

      }

      for (int num2 = 0; num2

Hmpff. Looks like my answer was truncated. Sorry about that!

Anyway, the point was that looking at the decompliation results, it's clear that at least in some cases the implementation is strictly linear.

However, if it was up to me, I'd actually vote for Eran's answer :)

In fact, I might just do that :)

You can just download the Reflector tool from http://www.aisto.com/roeder/dotnet/Download.aspx?File=Reflector and check it out yourself by looking at the String.IndexOf implementation.