ContainsメソッドやIndexOfメソッドではList内の要素を先頭から走査して一致する要素を検索します。　BinarySearchメソッドを使うと二分探索によって要素を検索することができます。

二分探索による検索では、あらかじめList内の要素がソートされていないと結果が不正となる一方、IndexOfメソッドよりも高速に検索を行うことができるという特徴があります(IndexOfやContainsはO(n)、BinarySearchはO(log n))。　格納されている要素が多数となる場合には二分探索による検索がより効果的です。

二分探索によってList内にある要素の位置を検索して取得する
using System;
using System.Collections.Generic;

class Sample {
  static void Main()
  {
    var list = new List<string>() {"Bob", "Alice", "Eve", "Charlie", "Dave"};

    // 二分探索を行う前にlistをソートされた状態にしておく
    list.Sort();

    // 値"Bob"を持つ要素の位置を取得する
    Console.WriteLine("BinarySearch(Bob) = {0}", list.BinarySearch("Bob"));

    // 値"Eve"を持つ要素の位置を取得する
    Console.WriteLine("BinarySearch(Eve) = {0}", list.BinarySearch("Eve"));

    // 存在しない値"Adam"の位置を取得する(負の値が返される)
    Console.WriteLine("BinarySearch(Adam) = {0}", list.BinarySearch("Adam"));
  }
}
実行結果
BinarySearch(Bob) = 1
BinarySearch(Eve) = 4
BinarySearch(Adam) = -1

Listとソートについては§.ソート (Sort)で解説します。