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

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

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

Class Sample
  Shared Sub Main()
    Dim list As New List(Of String)(New 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"))
  End Sub
End Class
実行結果
BinarySearch(Bob) = 1
BinarySearch(Eve) = 4
BinarySearch(Adam) = -1

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