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

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.