Articles   Members Online:
-Article/Tip Search
-News Group Search over 21 Million news group articles.
-Delphi/Pascal
-CBuilder/C++
-C#Builder/C#
-JBuilder/Java
-Kylix
Member Area
-Home
-Account Center
-Top 10 NEW!!
-Submit Article/Tip
-Forums Upgraded!!
-My Articles
-Edit Information
-Login/Logout
-Become a Member
-Why sign up!
-Newsletter
-Chat Online!
-Indexes NEW!!
Employment
-Build your resume
-Find a job
-Post a job
-Resume Search
Contacts
-Contacts
-Feedbacks
-Link to us
-Privacy/Disclaimer
Embarcadero
Visit Embarcadero
Embarcadero Community
JEDI
Links
ow to do a binary search on an alphasorted TListView Turn on/off line numbers in source code. Switch to Orginial background IDE or DSP color Comment or reply to this aritlce/tip for discussion. Bookmark this article to my favorite article(s). Print this article
31-Oct-02
Category
VCL-General
Language
Delphi 2.x
Views
103
User Rating
No Votes
# Votes
0
Replies
0
Publisher:
DSP, Administrator
Reference URL:
DKB
			Author: Tomas Rutkauskas

How to do a binary search on an alphasorted TListView

Answer:

If you want to use a fast searching algorithm (binary search for example) the 
listview has to be sorted on the column you do the duplicate check on. If it is not 
sorted you have to use the listviews FindCaption or FindData method, which does a 
linear search. To sort a listview use its AlphaSort or CustomSort methods.

A binary search on a alphasorted listview for a caption would be something like 
this (untested!):

1   {
2   Function ListviewBinarySearch
3   
4   Parameters:
5   
6   listview:
7   listview to search, assumed to be sorted, must be <> nil.
8   
9   Item:
10  item caption to search for, cannot be empty
11  
12  index:
13  returns the index of the found item, or the index where the item should be inserted 
14  if it is not already in the list. Returns True if there is an item with the passed 
15  caption in the list, false otherwise.
16  
17  Description:
18  Uses a binary search and assumes that the listview is sorted ascending on the 
19  caption of the listitems. The search is case-sensitive, like the default alpha-sort 
20  routine used by the TListview class.
21  
22  Note:
23  We use the lstrcmp function for string comparison since it is the function used by 
24  the default alpha sort routine. If the listview is sorted by another means (e.g. 
25  OnCompare event) this needs to be changed, the comparison method used must always 
26  be the same one used to sort the listview, or the search will not work!
27  
28  Error Conditions: none
29  Created: 31.10.99 by P. Below
30  }
31  
32  function ListviewBinarySearch(listview: TListview; const Item: string; var index:
33    Integer): Boolean;
34  var
35    first, last, pivot, res: Integer;
36  begin
37    Assert(Assigned(listview));
38    Assert(Length(item) > 0);
39    Result := false;
40    index := 0;
41    if listview.items.count = 0 then
42      Exit;
43    first := 0;
44    last := listview.items.count - 1;
45    repeat
46      pivot := (first + last) div 2;
47      res := lstrcmp(PChar(item), Pchar(listview.items[pivot].caption));
48      if res = 0 then
49      begin
50        { Found the item, return its index and exit. }
51        index := pivot;
52        result := true;
53        Break;
54      end
55      else if res > 0 then
56      begin
57        { Item is larger than item at pivot }
58        first := pivot + 1;
59      end
60      else
61      begin
62        { Item is smaller than item at pivot }
63        last := pivot - 1;
64      end;
65    until
66      last < first;
67    index := first;
68  end;


			
Vote: How useful do you find this Article/Tip?
Bad Excellent
1 2 3 4 5 6 7 8 9 10

 

Advertisement
Share this page
Advertisement
Download from Google

Copyright © Mendozi Enterprises LLC