Computer Science Canada

Binary Search Help
Author:  Qamar [ Tue Feb 24, 2009 8:59 pm ]
Post subject:  Binary Search Help
one of our assignments is to ask the user to enter in a last name to find from a text file, we have to take the text file and put it into an array... then call a function to do a binary search to find it... the code compiles fine, but when i call the function on line 19 it says the variable has no value...

Turing:

var lastname, firstname : array 1 .. 500 of string
var fin : int
var count := 0
open : fin, "sortedlist.txt", get
loop
    exit when eof (fin)
    count += 1
    get : fin, lastname (count), firstname (count)
    put lastname (count), " ", firstname (count)
end loop
close : fin

function bin_search (name : string) : int
    var hi, lo, mid : int
    hi := upper (lastname)
    lo := lower (lastname)
    mid := (hi + lo) div 2
    var x : int := -1
    if name > lastname (mid)  then 
        lo := mid + 1
    elsif name < lastname (mid) then
        hi := mid - 1
    end if

    if lo > hi then
        result x
    elsif name = lastname (mid) then
        result mid
    end if
end bin_search


var choice : string
put "what name are you looking for ?"
get choice
choice := Str.Upper (choice)

if bin_search (choice) = -1 then
    put choice, " is not on the list"
else
    put choice, " is number ", bin_search (choice)
end if
Author:  Tony [ Tue Feb 24, 2009 9:04 pm ]
Post subject:  RE:Binary Search Help
well, what are the values of all the variables used on that line?

Also, I'm really impressed by how your bin_search runs in O(1) Wink
Author:  Qamar [ Tue Feb 24, 2009 9:10 pm ]
Post subject:  Re: Binary Search Help
on the line, name is passed by choice, so that should be the name that is entered and lastname (mid) is the name on the array. and i made the array global. i'm not seeing why either of the variables shouldn't have a value. and ... thank you ? haha are i'm not sure if your joking about it being a binary search or not ... this is what our teacher called it.

edit: ops.. ignore the

Turing:

 put lastname (count), " ", firstname (count)


i just had that there to make sure that the file was going into the array.[/syntax]
Author:  Qamar [ Tue Feb 24, 2009 10:49 pm ]
Post subject:  Re: Binary Search Help
never mind... i got it to work... my mid wasn't being declared properly... so i had to figure out the actual max of the array... why wouldn't upper / lower work ?... because wouldn't it determine the beginning and the end of the array ?

here's my code...
Turing:

var lastname, firstname : array 1 .. 500 of string
var fin : int
var count := 0
open : fin, "sortedlist.txt", get
loop
    exit when eof (fin)
    count += 1
    get : fin, lastname (count), firstname (count)
end loop

function bin_search (name : string) : int
    var hi, lo, mid : int
    hi := count
    lo := 1

    var x : int := -1
    loop
        mid := (hi + lo) div 2

        exit when lo > hi or name = lastname (mid)
        if name > lastname (mid) then
            lo := mid + 1
        elsif name < lastname (mid) then
            hi := mid - 1
        end if
       
    end loop
    if lo > hi then
        result x
    end if
    if name = lastname (mid) then
        result mid
    end if
end bin_search


var choice : string
put "what name are you looking for ?"
get choice
choice := Str.Upper (choice)

if bin_search (choice) = -1 then
    put choice, " is not on the list"
else
    put choice, " is number ", bin_search (choice)
end if
close : fin

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy