# 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;
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!: ');
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.

• : 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;
: 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!: ');
: 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;
: : 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!: ');
: : 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.

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