----------------------------------- person Tue Mar 07, 2006 7:36 pm 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? 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 Tue Mar 07, 2006 9:05 pm ----------------------------------- 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 Tue Mar 07, 2006 10:02 pm ----------------------------------- 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 Tue Mar 07, 2006 10:47 pm ----------------------------------- 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 Tue Mar 07, 2006 11:44 pm ----------------------------------- 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 Wed Mar 08, 2006 11:09 am ----------------------------------- no, if i search for "Hiya", it shuld return 3 ----------------------------------- person Wed Mar 08, 2006 5:41 pm ----------------------------------- alrite, i solved my problem, turns out to be just a stupid typo, here's the one that works: 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 Wed Mar 08, 2006 6:55 pm ----------------------------------- You still don't need the length function. It's built into turing's string comparison. For example put ("hi" < "hippopotomus") put ("hia" < "hippopotomus") put ("hiz" < "hippopotomus") Your code could thus be simplified a lot.[/code] ----------------------------------- Cervantes Wed Mar 08, 2006 7:14 pm ----------------------------------- A couple of general notes, person. 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. Use descriptive names! What is "c"? What is "rL"? left and right should be local variables to the binary_search function. As soon as you find the value (if my_array (mid) = value) exit the loop/return your value. ----------------------------------- MysticVegeta Wed Mar 08, 2006 7:16 pm ----------------------------------- shouldnt take too long... that code is messed up 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 Wed Mar 08, 2006 7:54 pm ----------------------------------- 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 Wed Mar 08, 2006 9:21 pm ----------------------------------- How so is it not? From what I understand, it does the job :S ----------------------------------- Andy Wed Mar 08, 2006 9:22 pm ----------------------------------- and it's ridiculously slow... read what he wants Binary Search ----------------------------------- Cervantes Wed Mar 08, 2006 9:39 pm ----------------------------------- 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 Wed Mar 08, 2006 10:42 pm ----------------------------------- Pardon my stupidity but please do familiarize me with how to accomplish a faster version? Should I use quick sort instead of bubble? ----------------------------------- GlobeTrotter Thu Mar 09, 2006 12:27 am ----------------------------------- 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. ----------------------------------- MysticVegeta Thu Mar 09, 2006 2:36 pm ----------------------------------- eh I am not gonna be needing it anyways, since java already has a prebuilt binarysort method :) ----------------------------------- Andy Thu Mar 09, 2006 3:29 pm ----------------------------------- yes.. because using predefined methods you have no idea how to write is the way we promote things at this site