binary search

[person]

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

[iker]

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.

[GlobeTrotter]

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.

[person]

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

[MysticVegeta]

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?

[person]

no, if i search for "Hiya", it shuld return 3

[person]

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

[GlobeTrotter]

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]

[Cervantes]

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.
   

[MysticVegeta]

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

[Cervantes]

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?

[MysticVegeta]

How so is it not? From what I understand, it does the job :S

[Andy]

and it's ridiculously slow... read what he wants Binary Search

[Cervantes]

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.

[MysticVegeta]

Pardon my stupidity but please do familiarize me with how to accomplish a faster version? Should I use quick sort instead of bubble?