Search code examples
c#binary-searchlist-template

List<T>.BinarySearch returning a unexpected result

I'm getting an odd result from List.BinarySearch in a single case. When searching for for "$in" in a list where "$in" is present, the result is -4. Below is a test case which highlights the issue. Only the case looking for "$in" fails.

Could it be some sort of reserved keyword? I've compiled against .Net Framworks 3.5, 4.5.2 and 4.6 with the same result.

[TestMethod]
public void IssueWithBinarySearch() {
  List<string> operators = new List<string>( new[] { "$eq", "$gt", "$gte", "$lt", "$lte", "$ne", "$in", "$nin" } );

  Assert.AreEqual( 0, operators.BinarySearch( "$eq" ) );
  Assert.AreEqual( 1, operators.BinarySearch( "$gt" ) );
  Assert.AreEqual( 2, operators.BinarySearch( "$gte" ) );
  Assert.AreEqual( 3, operators.BinarySearch( "$lt" ) );
  Assert.AreEqual( 4, operators.BinarySearch( "$lte" ) );
  Assert.AreEqual( 5, operators.BinarySearch( "$ne" ) );
  Assert.AreEqual( 6, operators.BinarySearch( "$in" ) );
  Assert.AreEqual( 7, operators.BinarySearch( "$nin" ) );
}
Solution

  • Binary search works correctly with sorted list only. The List<T> must already be sorted; otherwise, the result is incorrect.