Computer Science Canada

binary search
Author:  person [ Tue Mar 07, 2006 7:36 pm ]
Post subject:  binary search
i don't understand why this binary search doesnt work, its supposed to search through a sorted alphabetical list and then put index value

can someone plz tell me wat's wrong with it?

code:

var names : array 1 .. 5 of string := init ("Bobby", "James", "Jamie", "Jill", "Tommy")
var left := 1
var right := 5
var name := "James"
proc rL (i, c : int, var right, left : int)
    for x : 1 .. i
        if name (x) < names (c) (x) then
            right := c - 1
            exit
        else
            left := c + 1
            exit
        end if
    end for
end rL
proc search
    var c : int := 0
    loop
        c := (left + right) div 2
        if names (c) = name then
            put c
        end if
        if length (names (c)) > length (name) then
            rL (length (name), c, right, left)
        else
            rL (length (names (c)), c, right, left)
        end if
        exit when left > right
    end loop
    put "not found"
end search
search

Author:  iker [ Tue Mar 07, 2006 9:05 pm ]
Post subject: 
I can tell you already just by looking at your code what the problem is. Your problem starts at your first procedure.

Try removing the word var. You don't have to declare that something is a variable in a procedure.
Also, you cannot alter the values of any parameters inside a procedure. You can only do this in a function.
You don't use the paramaters for left and right in your procedure unless your inputing data. Any outputed data from a procedure isn't in the pocedure paramaters.

You have a few minor problems with this code right now, hopefully this will help you a bit.
Author:  GlobeTrotter [ Tue Mar 07, 2006 10:02 pm ]
Post subject: 
Don't listen to iker, he is wrong. There are no syntaxical errors. You declared your variables correctly.

The issue is that you are comparing the lenghts of strings. I don't understand why you'd do this. Binary search has strings in order alphabetically, yet you are comparing lengths. This is likely the root of your problem.

You may want to consider using recursion for binary searching. I find it makes the coding simpler.
Author:  person [ Tue Mar 07, 2006 10:47 pm ]
Post subject: 
well, im checking the lengths because if i compare 2 words like:

Hi
Hippopotomus

first letter: same
second letter:same
third letter:Array Index Out of Bounds

so I need to make the loop go from 1 to the length of the shorter word
Author:  MysticVegeta [ Tue Mar 07, 2006 11:44 pm ]
Post subject: 
I dont understand, what are you trying to accomplish? You mean to say, if I have an array that has elements: {"Hello","Hey","Hiya"} and I need to search for "Hi" it should return 3?
Author:  person [ Wed Mar 08, 2006 11:09 am ]
Post subject: 
no, if i search for "Hiya", it shuld return 3
Author:  person [ Wed Mar 08, 2006 5:41 pm ]
Post subject: 
alrite, i solved my problem, turns out to be just a stupid typo, here's the one that works:

code:

var names : array 1 .. 5 of string := init ("Bobby", "James", "Jamie", "Jill", "Tommy")
var left := 1
var right := 5
var name := "James"
proc rL (i, c : int, var right, left : int)
    for x : 1 .. i
        if name (x) < names (c) (x) then
            right := c - 1
            exit
        elsif name (x) > names (c) (x) then
            left := c + 1
            exit
        end if
    end for
end rL
proc search
    var c : int := 0
    loop
        c := (left + right) div 2
        if names (c) = name then
            put c
        end if
        if length (names (c)) > length (name) then
            rL (length (name), c, right, left)
        else
            rL (length (names (c)), c, right, left)
        end if
        exit when left > right
    end loop
    put "not found"
end search
search
Author:  GlobeTrotter [ Wed Mar 08, 2006 6:55 pm ]
Post subject: 
You still don't need the length function. It's built into turing's string comparison.

For example

code:

put ("hi" < "hippopotomus")
put ("hia" < "hippopotomus")
put ("hiz" < "hippopotomus")


Your code could thus be simplified a lot.[/code]
Author:  Cervantes [ Wed Mar 08, 2006 7:14 pm ]
Post subject: 
A couple of general notes, person.

  1. A binary search is a function. It takes an array of elements and a value you are searching for, then returns the position of that value within the array, and returns a special value, such as 0 or -1, if the element is not found in the array. Thus, don't use a procedure.
  2. Use descriptive names! What is "c"? What is "rL"?
  3. left and right should be local variables to the binary_search function.
  4. As soon as you find the value (if my_array (mid) = value) exit the loop/return your value.
Author:  MysticVegeta [ Wed Mar 08, 2006 7:16 pm ]
Post subject: 
shouldnt take too long... that code is messed up
code:
var names : array 1 .. 5 of string := init ("Hi", "Hello", "Well", "What", "The")
var temp : string
const search := "The"
%Classic Bubble Sort
for i : 1 .. 5
    for j : i .. 5
        if (names (i) > names (j)) then
            temp := names (i)
            names (i) := names (j)
            names (j) := temp
        end if
    end for
end for
%Rest crap
for x : 1 .. upper (names)
    if names (x) = search then
        put x
        exit
    end if
    if x = upper (names) then
        put "Not found"
    end if
end for
Author:  Cervantes [ Wed Mar 08, 2006 7:54 pm ]
Post subject: 
MysticVegeta: That's not a binary search, You've got a sequential search.

Also, subroutines, subroutines, subroutines! Why throw all that code into the main program when it could go into a subroutine?

And then the next question to ask is, Why throw all those subroutines into the main program when they could go into a module?
Author:  MysticVegeta [ Wed Mar 08, 2006 9:21 pm ]
Post subject: 
How so is it not? From what I understand, it does the job :S
Author:  Andy [ Wed Mar 08, 2006 9:22 pm ]
Post subject: 
and it's ridiculously slow... read what he wants Binary Search
Author:  Cervantes [ Wed Mar 08, 2006 9:39 pm ]
Post subject: 
MysticVegeta wrote:
How so is it not? From what I understand, it does the job :S

It does search, but it is not a binary search. Saying your sequential search is the same as a binary search is like saying Turing is the same as O'Caml. Turing and O'Caml are both programming languages, just as sequential and binary searches are both searching algorithms. But O'Caml is far superior to Turing, and binary searches are far superior to sequential searches, on sorted data.
Author:  MysticVegeta [ Wed Mar 08, 2006 10:42 pm ]
Post subject: 
Pardon my stupidity but please do familiarize me with how to accomplish a faster version? Should I use quick sort instead of bubble?
Author:  GlobeTrotter [ Thu Mar 09, 2006 12:27 am ]
Post subject: 
no, that's not the issue. If you wanted to search sequentially, you wouldn't need to sort. Binary searches only work when a list is sorted.

Think of this example: guess a number between 1 and 100. each guess, I tell you whether you are too high, too low, or have it. You should be able to guess the answer within 7 guesses, no matter what.

Say the number is 49.

Your first guess should be 50 ((100 + 0) /2)

Since that guess is too high, you should then guess 25 ((0 + 50) / 2)

Since that guess is too low, you should then guess 37 ((25 + 50) / 2)

etc...


Now do the same thing with a sorted array.
Author:  MysticVegeta [ Thu Mar 09, 2006 2:36 pm ]
Post subject: 
eh I am not gonna be needing it anyways, since java already has a prebuilt binarysort method Smile
Author:  Andy [ Thu Mar 09, 2006 3:29 pm ]
Post subject: 
yes.. because using predefined methods you have no idea how to write is the way we promote things at this site

:


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

Terms of Use | Privacy Policy