BinarySearch is kickng my ***

Dev Shed Forums Sponsor:

1200+ fellow developers rate and compare features of the top IDEs, like Visual Studio, Eclipse, RAD, Delphi and others, across 13 categories. Enjoy this FREE Download of the IDE User Satisfaction Study by Evans Data Corporation. Download Now!

January 8th, 2008, 04:23 PM

RossR

Registered User

Join Date: Jan 2008

Posts: 3

Time spent in forums: 1 h 26 m 46 sec
Reputation Power: 0

BinarySearch is kickng my ***

hi guys, I've implemented this flawed code.

For a hangman game

The users 'guess' and the word to guess is passed to the binary Search,
the code is then supposed to search for the guess in theWord
to tell the user wether the guess they have chosen is present.

Code:


procedure binSearch(theWord : string; n : integer; guess : char); 


var 
  left, mid, right : integer; 


begin 
  left := 0; 
  right := n-1; 


  while (left <= right) do 
  begin 
    mid := (left + right) div 2; 
    if guess > theWord[mid] then 
      left := mid + 1 
    else if guess < theWord[mid] then 
      right := mid - 1 
    else 
      writeln('Found!'); 
      left := right + 1//creates a condition to terminate loop
  end; 
end;

procedure monkey(); 


var 
  cat : myArray; 
  choice, n : integer; 
  theWord : string; 
  guess : char; 


begin 
  choice := 1; 
  loadCat(cat); //loads the catergory 
  getEntry(cat, choice, theWord); //choses an entry from the category 
  n := length(theWord); //gets the length of theWord and sends it to 
the sort.
  sort(theWord, n);
  write('Take a guess!: '); 
  readln(guess); 
  binSearch(theWord, n, guess); 
end;

Help with this would be really really appreciated!

Many thanks in advance.

January 8th, 2008, 04:26 PM

medialint

spirit duplicator

Join Date: Apr 2004

Location: \\Firecrate\

Posts: 12,325

Folding Points: 232775 Folding Title: Super Ultimate Folder - Level 1

Time spent in forums: 4 Months 3 Weeks 12 h 8 m 19 sec
Reputation Power: 2578

So we're supposed to look at your wrong code, know what it's supposed to do and fix it so it does what you intended? That's all the info?

Hmmm ....

__________________
medialint.com

"Energy has the opportunity to change the climate if it's done right." - Sen. John Ensign, R-Nev. (quoted out of context)

January 8th, 2008, 04:34 PM

RossR

Registered User

Join Date: Jan 2008

Posts: 3

Time spent in forums: 1 h 26 m 46 sec
Reputation Power: 0

Quote:

Originally Posted by medialint

So we're supposed to look at your wrong code, know what it's supposed to do and fix it so it does what you intended? That's all the info?

Hmmm ....

Lol, sorry added some info at the top. Thanks for the reply.

January 8th, 2008, 10:50 PM

Schol-R-LEA

Commie Mutant Traitor

Join Date: Jun 2004

Location: The People's Republic of Berkeley

Posts: 1,083

Time spent in forums: 3 Weeks 4 Days 10 h 47 m 7 sec
Reputation Power: 446

Setting aside the errors in your implementation of the algorithm, I don't think that a binary search is going to work for this type of problem without more work. Binary chop only works if the data being searched through is sorted. For example, if you have a word 'supercilious' as the target the player is trying to guess, and the player guesses 'r', then a binary search through the word would go like this:

superc ilious : since the size of the word is even, we use the first letter before the split ('c'). Since ASCII 'r' is greater than ASCII 'c', we proceed to search the second half. (At this point, we've already hit the bug: the only 'r' is in the first half, but we can't find it.)
ili ous : the remaining section is again even, so we use the second 'i' as the mid-point. Since 'r' is greater than 'i', we search the fourth quarter.
u o s: The mid-point here is unequivocally 'o', which is less than 'r'. We continue with the part of the word remaining past the 'o'.
This leaves us with the last letter, 's', which isn't 'r', so the search fails.

Thus, to use a binary chop for this purpose, you would have to have a sorted copy of the word first:

sort('supercilious') => ceiiloprssuu
ceiilo prssuu : since the size of the word is even, we use the first letter before the split ('o'). Since ASCII 'r' is greater than ASCII 'o', we proceed to search the second half.
prs suu : the remaining section is again even, so we use the first 's' as the mid-point. Since 'r' is less than 's', we search the third quarter.
p r s: The mid-point here is unequivocally 'r', which is the sought letter. The search succeeds.

Note that you would want to have the sorted copy separate from the actual word, otherwise you would not be able to display it later. You will also need to remove or mark the letters which have been already found, since there may be more than one instance of them in the word.

To be honest, given the size of the searched data, a binary search is probably overkill, especially given that you need to sort it first; chances are, anything less than 100+ letters will be faster with a brute-force linear search. You'd have to check that yourself, but either way the difference is probably so small as to be effectively unmeasurable.

__________________
Rev First Speaker Schol-R-LEA;2 JAM LCF ELF KoR KCO BiWM TGIF
#define KINSEY (rand() % 7) λ Scheme is the Red Pill
Scheme in Short • Understanding the C/C++ Preprocessor
Taming Python • A Highly Opinionated Review of Programming Languages for the Novice, v1.1

FOR SALE: One ShapeSystem 2300 CMD, extensively modified for human use. Includes s/w for anthro, transgender, sex-appeal enhance, & Gillian Anderson and Jason D. Poit clone forms. Some wear. $4500 obo. tverres@et.ins.gov

Last edited by Schol-R-LEA : January 8th, 2008 at 10:55 PM.

January 9th, 2008, 06:09 PM

RossR

Registered User

Join Date: Jan 2008

Posts: 3

Time spent in forums: 1 h 26 m 46 sec
Reputation Power: 0

Quote:

Originally Posted by Schol-R-LEA

superc ilious : since the size of the word is even, we use the first letter before the split ('c'). Since ASCII 'r' is greater than ASCII 'c', we proceed to search the second half. (At this point, we've already hit the bug: the only 'r' is in the first half, but we can't find it.)
ili ous : the remaining section is again even, so we use the second 'i' as the mid-point. Since 'r' is greater than 'i', we search the fourth quarter.
u o s: The mid-point here is unequivocally 'o', which is less than 'r'. We continue with the part of the word remaining past the 'o'.
This leaves us with the last letter, 's', which isn't 'r', so the search fails.

Thus, to use a binary chop for this purpose, you would have to have a sorted copy of the word first:

sort('supercilious') => ceiiloprssuu
ceiilo prssuu : since the size of the word is even, we use the first letter before the split ('o'). Since ASCII 'r' is greater than ASCII 'o', we proceed to search the second half.
prs suu : the remaining section is again even, so we use the first 's' as the mid-point. Since 'r' is less than 's', we search the third quarter.
p r s: The mid-point here is unequivocally 'r', which is the sought letter. The search succeeds.

Thanks for your reply. This 'issue' has now been resolved. You are correct, binary Search is overkill for what I want, I just had an opportunity to do (because part of this program requires a search) so i thought i'd give it a try. I did sort the string into characters of ascending alphabetical order already, but nm.When I posted this original thread last night I was very tired and exhausted and my brain had sizzled (meltdown was greater than it is now!) I left many details out of the background to do with the code.

Thread Tools	Search this Thread
Email this Page	Search this Thread: Advanced Search
Display Modes	Rate This Thread
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode	Rate This Thread: