Binary Searching a TList that contains items with a value of nil.

Hi all,
I have a TList that I need to perform a binary search on.
The problem is that some items in the list contain nil,  (are purposely assigned nil). For the ones that are populated we have a pointer to a floating point value that we are searching for.
The list cannot be sorted prior to the search, and the nil values cannot be removed prior to searching.
We basically need to return the index of the matching item, but obviously we are unable to perform any comparisons using the items that are nil.
Can anyone offer a modified binary search function that will handle the nil items in the list?
Hope this makes sense...

Cheers





LVL 2
insomniac92Asked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Emmanuel PASQUIERFreelance Project ManagerCommented:
Type
 pFloat=^Double;

function SearchFloatInList(List:TList;Value:Double):Integer;
begin
 for Result:=0 to List.Count-1 do if Assigned(List[Result]) do
  begin
   if pFloat(List[Result])^=Value Then Exit;
  end;
 Result:=-1;
end;
0
insomniac92Author Commented:
Thanks, but it has to be a binary search. i.e. half the list, is the value we are looking for <> current value, half the list again, etc...
Speed is very important.
Thanks
0
cyberkiwiCommented:
Hi insomniac,

I know you mentioned that the list cannot be sorted before searching, but is the list itself already sorted in any way? i.e. disregarding the nil values, are the non-nil values sorted?
Binary searching only works on sorted lists!  Otherwise you will need to inspect each and every item to find the match.
0
Build an E-Commerce Site with Angular 5

Learn how to build an E-Commerce site with Angular 5, a JavaScript framework used by developers to build web, desktop, and mobile applications.

insomniac92Author Commented:
Hi, yes, the list is sorted by the floating point values. They are actually datetime values.
0
cyberkiwiCommented:
Some code from http://www.delphipages.com/forum/showthread.php?t=103554
function BinSearch(AList: TList; AValue: double) : Integer;
type pDbl = ^double;
var
First : Integer;
Last : Integer;
Pivot : Integer;
Found : Boolean;

begin
First := Low(AList); //Sets the first item of the range
Last := High(AList); //Sets the last item of the range
Found := False; //Initializes the Found flag (Not found yet)
Result := -1; //Initializes the Result

//If First > Last then the searched item doesn't exist
//If the item is found the loop will stop
While (First <= Last) and (not Found) do
begin
//Gets the middle of the selected range
Pivot := (First + Last) div 2;
while not Assigned(pDbl(AList[Pivot])) and (Pivot > First) do
  Pivot=Pivot-1;
if not Assigned(pDbl(AList[Pivot])) then
begin
  // the entire bottom half has been searched
  First := (First + Last) div 2 +1;
  Continue; // search the top half
end;
// not sure if this converges! test

//Compares the String in the middle with the searched one
If pDbl(AList[Pivot])^ = AValue then
begin
Found := True;
Result := Pivot;
end
//If the Item in the middle has a bigger value than
//the searched item, then select the first half
else If pDbl(AList[Pivot])^ > AValue then
Last := Pivot - 1
//else select the second half
else First := Pivot + 1;
end;
end;

Open in new window

0
Emmanuel PASQUIERFreelance Project ManagerCommented:
you are talking about dichotomic search, ok ! I didn't knew the use of the term binary for this, and wikipedia helped as always :o)

The added difficulty are your nil values along the way. Cyberwiki algo might get stuck in an infinite loop  because he only 'trim' them in one direction. You need 2 'pivot' for this
function BinSearch(AList: TList; AValue: double) : Integer;
Var
 First,Last,PivotMin,PivotMax:Integer;
 PivotValue:Double;
begin
 First:=0;
 Last:=AList.Count-1;
 Result:=-1; // by default, -1 => not found

 While First<=Last do
  begin
   PivotMin:=(First + Last) div 2;
   PivotMax:=PivotMin+1;

   while (PivotMin>=First) And Not Assigned(AList[PivotMin]) do Dec(PivotMin); 
   if PivotMin>=First Then
    begin
     PivotValue:=pDbl(AList[PivotMin])^;
     if PivotValue = AValue then
      begin
       Result:=PivotMin;
       Exit;
      end;
     if AValue < PivotValue then 
      begin
       Last:=PivotMin-1;
       continue;
      end;
    end;

   while (PivotMax<=Last) And Not Assigned(AList[PivotMax]) do Inc(PivotMax);
   if PivotMax<=Last Then
    begin
     PivotValue:=pDbl(AList[PivotMax])^;
     if PivotValue = AValue then
      begin
       Result:=PivotMax;
       Exit;
      end;
    end;
   if AValue > PivotValue then 
    begin
     First:=PivotMax+1;
     continue;
    end;
// Here : list sort error : AList[PivotMax]<AList[PivotMin]
// or both sub list are full of nil values
   Exit;
  end;
end;   

Open in new window

0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
cyberkiwiCommented:
Hi epasquier,

I haven't got Delphi on hand  where I am but "might" is the operative word isn't it! I believe that it does converge, because whatever else happens, the range always shrinks - if it completely exhausts the branch being trimmed, the range (First-> +1) is still collapsed.
0
Emmanuel PASQUIERFreelance Project ManagerCommented:
@ciberwiki, on deeper thought, yes you are right. I wrongly assumed you could have a problem because you don't have a second pivot, but on the case you hit a dense zone of nil, and need to go back, you recalculate your pivot position before starting a new loop :

if not Assigned(pDbl(AList[Pivot])) then
begin
  // the entire bottom half has been searched
  First := (First + Last) div 2 +1;

so you won't have a loop problem. But since you don't exclude 'bubbles of void' zones around the pivot, there are cases where your algo will check many times the nil state of the same list item.
The range always shrink, but some times you could make it shrink faster to completely exclude a bubble found in the first step.
0
insomniac92Author Commented:
Hi epasquier and cyberkiwi
I increased the points to 350 and gave cyberkiwi 100, and 250 to epasquier as this was the solution I went with.
Thanks both for your help.
Cheers
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Delphi

From novice to tech pro — start learning today.