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

novabondnovabond 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
while (not Found) and (High - Low >= 0) 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]

Comments

  • Phat NatPhat Nat 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
    while (not Found) and (High - Low >= 0) 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]

Sign In or Register to comment.