Problem with Binary Search.

I'm using the binary Search.


[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!');
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;

[/code]

I know that when the correct guess is found, left will be
smaller than right and therefore I have an infinite loop, but I am
just lost as to how I can deal with the results of the binary Search
(what to do if I find the value or don't find the value).

Some help with this would be greatly appreciated. Thanks in advance.

Comments

  • : I'm using the binary Search.
    :
    :
    : [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!');
    : 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;
    :
    : [/code]:
    :
    : I know that when the correct guess is found, left will be
    : smaller than right and therefore I have an infinite loop, but I am
    : just lost as to how I can deal with the results of the binary Search
    : (what to do if I find the value or don't find the value).
    :
    : Some help with this would be greatly appreciated. Thanks in advance.
    :
    :
    Normally the loop ends only if (left = right) or (left+1 = right). As long as the loop is running, you need to update the left/right. You can make a shortcut by checking if (word[mid] = guess) and set left and right to mid (ending the loop). But you [b]must[/b] change either left or right (or both) on each iteration of the loop, thereby making the loop finite in all cases.
    After the loop, you check if either (word[left] = guess) or (word[right] = guess). Based on the result of that if-then you can give the index of the result or some indication that the guess wasn't found.
  • : : I'm using the binary Search.
    : :
    : :
    : : [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!');
    : : 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;
    : :
    : : [/code]: :
    : :
    : : I know that when the correct guess is found, left will be
    : : smaller than right and therefore I have an infinite loop, but I am
    : : just lost as to how I can deal with the results of the binary Search
    : : (what to do if I find the value or don't find the value).
    : :
    : : Some help with this would be greatly appreciated. Thanks in advance.
    : :
    : :
    : Normally the loop ends only if (left = right) or (left+1 = right).
    : As long as the loop is running, you need to update the left/right.
    : You can make a shortcut by checking if (word[mid] = guess) and set
    : left and right to mid (ending the loop). But you [b]must[/b] change
    : either left or right (or both) on each iteration of the loop,
    : thereby making the loop finite in all cases.
    : After the loop, you check if either (word[left] = guess) or
    : (word[right] = guess). Based on the result of that if-then you can
    : give the index of the result or some indication that the guess
    : wasn't found.


    Thanks for your reply.

    Sorry though I am still a bit confused, so does this mean in my else case in the loop, I have to say that left := mid; right := mid?

  • : : : I'm using the binary Search.
    : : :
    : : :
    : : : [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!');
    : : : 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;
    : : :
    : : : [/code]: : :
    : : :
    : : : I know that when the correct guess is found, left will be
    : : : smaller than right and therefore I have an infinite loop, but I am
    : : : just lost as to how I can deal with the results of the binary Search
    : : : (what to do if I find the value or don't find the value).
    : : :
    : : : Some help with this would be greatly appreciated. Thanks in advance.
    : : :
    : : :
    : : Normally the loop ends only if (left = right) or (left+1 = right).
    : : As long as the loop is running, you need to update the left/right.
    : : You can make a shortcut by checking if (word[mid] = guess) and set
    : : left and right to mid (ending the loop). But you [b]must[/b] change
    : : either left or right (or both) on each iteration of the loop,
    : : thereby making the loop finite in all cases.
    : : After the loop, you check if either (word[left] = guess) or
    : : (word[right] = guess). Based on the result of that if-then you can
    : : give the index of the result or some indication that the guess
    : : wasn't found.
    :
    :
    : Thanks for your reply.
    :
    : Sorry though I am still a bit confused, so does this mean in my else
    : case in the loop, I have to say that left := mid; right := mid?
    :
    :
    Almost right. In your case you need to make left larger than right, since the loop continues to run if right = left. Or you can set left and right to mid and change the loop so that it will stop if left = right or left+1 = right.
  • : : : : I'm using the binary Search.
    : : : :
    : : : :
    : : : : [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!');
    : : : : 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;
    : : : :
    : : : : [/code]: : : :
    : : : :
    : : : : I know that when the correct guess is found, left will be
    : : : : smaller than right and therefore I have an infinite loop, but I am
    : : : : just lost as to how I can deal with the results of the binary Search
    : : : : (what to do if I find the value or don't find the value).
    : : : :
    : : : : Some help with this would be greatly appreciated. Thanks in advance.
    : : : :
    : : : :
    : : : Normally the loop ends only if (left = right) or (left+1 = right).
    : : : As long as the loop is running, you need to update the left/right.
    : : : You can make a shortcut by checking if (word[mid] = guess) and set
    : : : left and right to mid (ending the loop). But you [b]must[/b] change
    : : : either left or right (or both) on each iteration of the loop,
    : : : thereby making the loop finite in all cases.
    : : : After the loop, you check if either (word[left] = guess) or
    : : : (word[right] = guess). Based on the result of that if-then you can
    : : : give the index of the result or some indication that the guess
    : : : wasn't found.
    : :
    : :
    : : Thanks for your reply.
    : :
    : : Sorry though I am still a bit confused, so does this mean in my else
    : : case in the loop, I have to say that left := mid; right := mid?
    : :
    : :
    : Almost right. In your case you need to make left larger than right,
    : since the loop continues to run if right = left. Or you can set left
    : and right to mid and change the loop so that it will stop if left =
    : right or left+1 = right.

    Thanks for your reply again.

    I placed left := right + 1; to try and terminate the loop, Into the else case and nothing happens when I search for a character which is in the word.


  • : : : : : I'm using the binary Search.
    : : : : :
    : : : : :
    : : : : : [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!');
    : : : : : 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;
    : : : : :
    : : : : : [/code]: : : : :
    : : : : :
    : : : : : I know that when the correct guess is found, left will be
    : : : : : smaller than right and therefore I have an infinite loop, but I am
    : : : : : just lost as to how I can deal with the results of the binary Search
    : : : : : (what to do if I find the value or don't find the value).
    : : : : :
    : : : : : Some help with this would be greatly appreciated. Thanks in advance.
    : : : : :
    : : : : :
    : : : : Normally the loop ends only if (left = right) or (left+1 = right).
    : : : : As long as the loop is running, you need to update the left/right.
    : : : : You can make a shortcut by checking if (word[mid] = guess) and set
    : : : : left and right to mid (ending the loop). But you [b]must[/b] change
    : : : : either left or right (or both) on each iteration of the loop,
    : : : : thereby making the loop finite in all cases.
    : : : : After the loop, you check if either (word[left] = guess) or
    : : : : (word[right] = guess). Based on the result of that if-then you can
    : : : : give the index of the result or some indication that the guess
    : : : : wasn't found.
    : : :
    : : :
    : : : Thanks for your reply.
    : : :
    : : : Sorry though I am still a bit confused, so does this mean in my else
    : : : case in the loop, I have to say that left := mid; right := mid?
    : : :
    : : :
    : : Almost right. In your case you need to make left larger than right,
    : : since the loop continues to run if right = left. Or you can set left
    : : and right to mid and change the loop so that it will stop if left =
    : : right or left+1 = right.
    :
    : Thanks for your reply again.
    :
    : I placed left := right + 1; to try and terminate the loop, Into the
    : else case and nothing happens when I search for a character which is
    : in the word.
    :
    :
    :
    Beware that binary search only works for sorted lists. For unsorted lists you need to use naive search algorithms.
    Also note that strings are 1-indexed in Pascal.
  • : : : : : : I'm using the binary Search.
    : : : : : :
    : : : : : :
    : : : : : : [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!');
    : : : : : : 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;
    : : : : : :
    : : : : : : [/code]: : : : : :
    : : : : : :
    : : : : : : I know that when the correct guess is found, left will be
    : : : : : : smaller than right and therefore I have an infinite loop, but I am
    : : : : : : just lost as to how I can deal with the results of the binary Search
    : : : : : : (what to do if I find the value or don't find the value).
    : : : : : :
    : : : : : : Some help with this would be greatly appreciated. Thanks in advance.
    : : : : : :
    : : : : : :
    : : : : : Normally the loop ends only if (left = right) or (left+1 = right).
    : : : : : As long as the loop is running, you need to update the left/right.
    : : : : : You can make a shortcut by checking if (word[mid] = guess) and set
    : : : : : left and right to mid (ending the loop). But you [b]must[/b] change
    : : : : : either left or right (or both) on each iteration of the loop,
    : : : : : thereby making the loop finite in all cases.
    : : : : : After the loop, you check if either (word[left] = guess) or
    : : : : : (word[right] = guess). Based on the result of that if-then you can
    : : : : : give the index of the result or some indication that the guess
    : : : : : wasn't found.
    : : : :
    : : : :
    : : : : Thanks for your reply.
    : : : :
    : : : : Sorry though I am still a bit confused, so does this mean in my else
    : : : : case in the loop, I have to say that left := mid; right := mid?
    : : : :
    : : : :
    : : : Almost right. In your case you need to make left larger than right,
    : : : since the loop continues to run if right = left. Or you can set left
    : : : and right to mid and change the loop so that it will stop if left =
    : : : right or left+1 = right.
    : :
    : : Thanks for your reply again.
    : :
    : : I placed left := right + 1; to try and terminate the loop, Into the
    : : else case and nothing happens when I search for a character which is
    : : in the word.
    : :
    : :
    : :
    : Beware that binary search only works for sorted lists. For unsorted
    : lists you need to use naive search algorithms.
    : Also note that strings are 1-indexed in Pascal.

    I put the string through a sorting algorithm before using the binary search on the string. Oh what does 1-indexed mean?

  • : I'm using the binary Search.
    :
    :
    : [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!');
    : 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;
    :
    : [/code]:
    :
    : I know that when the correct guess is found, left will be
    : smaller than right and therefore I have an infinite loop, but I am
    : just lost as to how I can deal with the results of the binary Search
    : (what to do if I find the value or don't find the value).
    :
    : Some help with this would be greatly appreciated. Thanks in advance.
    :
    :
    The first character is word[1], the second is word[2], etc. This is opposed to 0-indexed, which is more common in lists and strings of other languages. In 0-indexed lists the first element is list[0], second is list[1], etc.
  • : : I'm using the binary Search.
    : :
    : :
    : : [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!');
    : : 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;
    : :
    : : [/code]: :
    : :
    : : I know that when the correct guess is found, left will be
    : : smaller than right and therefore I have an infinite loop, but I am
    : : just lost as to how I can deal with the results of the binary Search
    : : (what to do if I find the value or don't find the value).
    : :
    : : Some help with this would be greatly appreciated. Thanks in advance.
    : :
    : :
    : The first character is word[1], the second is word[2], etc. This is
    : opposed to 0-indexed, which is more common in lists and strings of
    : other languages. In 0-indexed lists the first element is list[0],
    : second is list[1], etc.

    Oh okay, thanks. I just changed the initialization on left to 1 and right to n, but this still won't work :(


Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories