Binary Search?

[zoltrix]

I have to do a simple binary search for my Comp Sci class (Grade 12). Only problem i have is that my teacher hasn't taught the course in the past 5 years so he's a bit rusty. ex - he has no idea what he's doing.

Can someone tell me how to do a simple binary search? I tried looking it up here in the tutorials but i cant seem to find what im looking for.

P.S - I know Java, not Turing. Only reason im doing Turing is because my teacher totally forgot Java, and knows a bit of Turing


The assignment is i have to have one program ask the user to input 25 names. The next program alphabetizes them. And the last is a binary search where the user types in a name and it tells them what slot it's in. I have the first 2 done, but not the last. Any help?

BinarySearchWriteFile.t wrote:

%Output a File
var sn : int := 0 %Stream number "channel"
var name : string := " " %Reads line of input
var age : int := 0 %Reads line of input
open : sn, "BinarySearch.txt", put %Writes to file.
loop
put "Enter name: " ..
get name : *
exit when name = "quit"
put : sn, name
end loop
close : sn

BinarySearchReadNames.t wrote:

%reads lines of text from BinarySearch
var sn : int := 0 %Stream number "channel"
var linenumber : int := 0 %Counter
var list : array 1 .. 9 of string
var temp : string
open : sn, "BinarySearch.txt", get %Open file to read.
loop
exit when eof (sn) %checks the end of file
linenumber := linenumber + 1
get : sn, list (linenumber) : * % Reads an entire line of text
put linenumber : 3, " ", list (linenumber)
end loop
close : sn
for decreasing last : 9 .. 2
var sorted : boolean := true
for i : 1 .. last - 1
if list (i) > list (i + 1) then
sorted := false
temp := list (i)
list (i) := list (i + 1)
list (i + 1) := temp
end if
end for
exit when sorted
end for
put skip
for i : 1 .. 9
put i : 3, " ", list (i)
end for

[Tony]

zoltrix @ Wed Apr 16, 2008 9:20 pm wrote:

I know Java, not Turing.

Binary Search is an idea that's language independent, so this shouldn't make a difference.

Classically one would think of this in terms of Binary Trees, but for the sake of simplicity of implementation, a binary tree could be represented by a flat array. Your list is already sorted. You start in the middle, and see if the word you are looking for higher or lower. Then you only consider that half of the list and recursively repeat the step until you find your index.

[zoltrix]

Sounds easy enough.

How do i only focus on that half of the list though?

bunch of if else statements?

[A.J]

you're doing Binary Search in Gr.12 !
anyways.....the basic idea of binary search is to keep splitting the list you're searching in into half, and perfoming the following recursive approach:
1).Check if the middle term of section being searched is the item you're searching.
2). If it is, then you're done. else, if it is less than the middle term, do steps 1 and 2 for the section from the term after the middle term - the last term. If it is greater than the middle term, than do steps 1 and 2 for the section from ter #1 to the term before the middle term.

In turing, it would be:

Turing:

proc binarysearch (first, last, searchedterm : int)     var middle := (first + last) div 2     if nums (middle) = searchedterm then         put "Done. Term found"     elsif nums (middle) < searchedterm then         binarysearch (middle + 1, last, searchedterm)     elsif nums (middle) > searchedterm then         binarysearch (first, middle - 1, searchedterm)     end if end binarysearch

Of course your array should be sorted at the beginning for the whole thing to work
You should also add a bit more to the procedure in case your term isn't found. I'll leave that to you.

[zoltrix]

Here is my final program Thanks for all the help guys.

Now i just have to figure out how to make my last put line only come up when needed.

Turing:

%reads lines of text from BinarySearch var sn : int := 0 %Stream number "channel" var linenumber : int := 0 %Counter var list : array 1 .. 9 of string var temp : string open : sn, "BinarySearch.txt", get %Open file to read. loop     exit when eof (sn) %checks the end of file     linenumber := linenumber + 1     get : sn, list (linenumber) : * % Reads an entire line of text     put linenumber : 3, " ", list (linenumber) end loop close : sn for decreasing last : 9 .. 2     var sorted : boolean := true     for i : 1 .. last - 1         if list (i) > list (i + 1) then             sorted := false             temp := list (i)             list (i) := list (i + 1)             list (i + 1) := temp         end if     end for     exit when sorted end for put skip for i : 1 .. 9     put i : 3, " ", list (i) end for var first, last : int first := 1 last := 9 var searchedterm : string put "What name do you want to search? " get searchedterm var middle : int loop     middle := (first + last) div 2     if searchedterm = list (middle) then         put "Done. Term found"         exit     elsif searchedterm > list (middle) then         first := middle     elsif searchedterm < list (middle) then         last := middle     end if     exit when (middle = first and middle + 1 = last) or (middle = last and middle = first) end loop     put "Name not found."

[zoltrix]

alright well it's not 100% final, but it's looking really good. i just have to figure out a way for the array to be an unknown variable that will be set once the user stops entering names. Say the user enters 30 names, the array size is 30. Anyone know how to do that?

[Tony]

flexible arrays

[zoltrix]

Sounds good. Thanks, i'll look it up

Thanks for the help again guys. I really appreciate it.