TList.BinarySearch Method (T, Integer)

Search sorted list for element using binary search.

Pascal

function BinarySearch(const Item: T; out Index: Integer): Boolean; overload;
function BinarySearch(const Item: T; out Index: Integer; const AComparer: IComparer<T>): Boolean; overload;

C++

__fastcall Boolean BinarySearch(const T Item, int Index);
__fastcall Boolean BinarySearch(const T Item, int Index, const IComparer<T> AComparer);

Description

The overloaded method BinarySearch searches for the list element Item using a binary search. The method returns true if it finds the element and false otherwise. If found, Index contains the zero-based index of Item. If not found, Index contains the index of the first entry larger than Item.

Note: BinarySearch requires that the list be sorted. The IndexOf method does not require a sorted list, but is usually slower than BinarySearch.

If there is more than one element in the list equal to Item, the index of the first match is returned in Index. This is the index of any of the matching items, not necessarily the first.

A comparison function AComparer may be provided to compare elements.

If Item is out of the range of the list, an EArgumentOutOfRangeException exception is raised.

This is an O(log n) operation for a list with n entries.

Delphi Examples:

Copy Code

{
This example demonstrates the usage of the generic TList class.
}
procedure TForm3.Button1Click(Sender: TObject);
var
  List: TList<Integer>;
  FoundIndex: Integer;
begin
  { Create a new List }
  List := TList<Integer>.Create();
  { Register a notification call-back }
  List.OnNotify := ListChanged;
  { Add a few values to the list }
  List.AddRange([5, 1, 8, 2, 9, 14, 4, 5, 1]);

  MessageDlg('Index of first 1 is ' + IntToStr(List.IndexOf(1)),
    mtInformation, [mbOK], 0);
  MessageDlg('Index of last 1 is ' + IntToStr(List.LastIndexOf(1)),
    mtInformation, [mbOK], 0);
  MessageDlg('List contains elemnt 100? ' + BoolToStr(List.Contains(100)),
    mtInformation, [mbOK], 0);

  { Add another element to the list }
  List.Add(100);

  MessageDlg('There are ' + IntToStr(List.Count) + ' elements in the list.',
    mtInformation, [mbOK], 0);

  { Remove the first occurence of 1 }
  List.Remove(1);
  { Delete a few elements form position 0 }
  List.Delete(0);
  List.DeleteRange(0, 2);
  { Extract the remeining 1 from the list }
  List.Extract(1);
  { Set the capacity to the actual length }
  List.TrimExcess();
  MessageDlg('There capacity of the list is ' + IntToStr(List.Capacity),
    mtInformation, [mbOK], 0);

  { Clear the list }
  List.Clear();
  { Insert some elements }
  List.Insert(0, 2);
  List.Insert(1, 1);
  List.InsertRange(0, [6, 3, 8, 10, 11]);

  { Sort the list }
  List.Sort();

  { Binary search for the required element }
  if List.BinarySearch(6, FoundIndex) then
    MessageDlg('Found element 6 at index ' + IntToStr(FoundIndex), mtInformation, [mbOK], 0);

  { Reverse the list }
  List.Reverse();
  MessageDlg('The element on position 0 is ' + IntToStr(List.Items[0]), mtInformation, [mbOK], 0);
end;

procedure TForm3.ListChanged(Sender: TObject; const Item: Integer; Action: TCollectionNotification);
begin
  { This method is called by the List everytime a change occurs }
  if Action = cnAdded then
     MessageDlg('Element added: ' + IntToStr(Item), mtInformation, [mbOK], 0)
  else if Action = cnRemoved then
     MessageDlg('Element removed: ' + IntToStr(Item), mtInformation, [mbOK], 0)
  else if Action = cnExtracted then
     MessageDlg('Element extracted: ' + IntToStr(Item), mtInformation, [mbOK], 0)
end;