Binary Searching using recursion - Programmers Heaven

#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

# Binary Searching using recursion

Posts: 12Member
[b][red]This message was edited by Moderator at 2003-4-24 5:26:7[/red][/b][hr]
Hello. I have a binary searching function which i will post in a second, but I would like to convert it to use recursion. I am not really good with working with recursion and i really don't know what to do. Thanks to anyone who can guide me or write some code :-)

[code]
function Search(var List:ListType; ItemSought: ItemType): Integer;
{ List is already in order from low to high here and returns }
{ the index of the location where itemsought is, or 0 if not }
{ found }
var
Low, High, Middle: Integer;
Found: Boolean;
begin
Low := 1;
High := List.NumItems;
Found := FALSE;
with List do
begin
Middle := (Low + High) div 2;
if ItemSought < Item[Middle]
then High := Middle - 1}
else if ItemSought > Item[Middle]
then Low := Middle + 1
else Found := TRUE
end;
if List.Item[Middle] = ItemSought
then Search := Middle
else Search := 0
end;
[/code]

thanks to anyone who can help me here.

[Red]*Edited by Moderator to add formatting tags[/Red]

• Posts: 757Member
[b][red]This message was edited by Phat Nat at 2003-4-26 1:43:48[/red][/b][hr]
: [b][red]This message was edited by Moderator at 2003-4-24 5:26:7[/red][/b][hr]
: Hello. I have a binary searching function which i will post in a second, but I would like to convert it to use recursion. I am not really good with working with recursion and i really don't know what to do. Thanks to anyone who can guide me or write some code :-)
:

This is one example. Not the greatest, but it works and will show you the basics. [b]Search[/b] is your code and [b]Search2[/b] is the Recursive function. I have just made some basic values (mutiples of 2) for demo purposes. The FALSE statements should return 0 because they are odd and the TRUE statements should return the position number.

Phat Nat

[code]
TYPE
ItemType = Byte;
ListType = record
NumItems : Integer;
Item : Array[1..50] Of ItemType;
End;

VAR
MyList : ListType;
X : Word;

function Search(var List:ListType; ItemSought: ItemType): Integer;
{ List is already in order from low to high here and returns }
{ the index of the location where itemsought is, or 0 if not }
{ found }
var
Low, High, Middle: Integer;
Found: Boolean;

begin
Low := 1;
High := List.NumItems;
Found := FALSE;
with List do
begin
Middle := (Low + High) div 2;
if ItemSought < Item[Middle]
then High := Middle - 1
else if ItemSought > Item[Middle]
then Low := Middle + 1
else Found := TRUE
end;
if List.Item[Middle] = ItemSought
then Search := Middle
else Search := 0
end;

function Search2(var List:ListType; ItemSought: ItemType): Integer;
{ List is already in order from low to high here and returns }
{ the index of the location where itemsought is, or 0 if not }
{ found }
var
Low, High, Middle: Integer;
Found: Boolean;

FUNCTION FindIt(Low, High : Integer) : Integer;
Begin
Middle := (High-Low) div 2 + Low;
With List do
If ItemSought = Item[Middle] Then { We found it! }
FindIt := Middle
ELSE If (Low = High) Then { Didn't Find Anything }
FindIt := 0
ELSE If (Low = Middle) Then { Don't forget top value }
FindIt := FindIt(High,High)
ELSE If ItemSought < Item[Middle] Then { Need to go Lower }
FindIt := FindIt(Low,Middle)
ELSE If ItemSought > Item[Middle] Then { Need to go Higher }
FindIt := FindIt(Middle,High);
End;

begin
Low := 1;
High := List.NumItems;
Found := FALSE;
Search2 := FindIt(Low,High);
end;

Begin
MyList.NumItems := 50;
For X := 1 to 50 Do
MyList.Item[X] := X*2;
Writeln;
WriteLn('FALSE=',Search (MyList,1));
WriteLn('FALSE=',Search2(MyList,1));
WriteLn(' TRUE=',Search (MyList,2));
WriteLn(' TRUE=',Search2(MyList,2));
WriteLn(' TRUE=',Search (MyList,94));
WriteLn(' TRUE=',Search2(MyList,94));
WriteLn('FALSE=',Search (MyList,97));
WriteLn('FALSE=',Search2(MyList,97));
WriteLn(' TRUE=',Search (MyList,100));
WriteLn(' TRUE=',Search2(MyList,100));
End.
[/code]