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!

#### Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

# 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]