# 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
###### Who is Participating?

Freelance 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;

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;
``````
0

Freelance 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

Author 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

Commented:
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

Author Commented:
Hi, yes, the list is sorted by the floating point values. They are actually datetime values.
0

Commented:
``````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
Result := -1; //Initializes the Result

//If First > Last then the searched item doesn't exist
//If the item is found the loop will stop
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;
``````
0

Commented:
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

Freelance 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

Author 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.