I am studying computer science (distance learning) and am confused about an "extra info question" that appears in the textbook but which has no answer. It's regarding the linear search algorithm and short circuit evaluation.
The algorithm for a linear search in the book is written as follows:
pointer = 0
WHILE pointer < LengthOfList AND list[pointer] != searchedfor:
------ Add one to pointer
ENDWHILE
IF pointer >= LengthOfList THEN:
------- PRINT("Item is not in the list")
ELSE
------- PRINT("Item is at location " +pointer)
ENDIF
In the extra info box it talks about short circuit evaluation and how when there are multiple parts linked by Boolean operators the computer only evaluates the second condition if it is necessary. So I get that with Condition 1 AND Condition 2 (when using short circuit evaluation) Condition 2 will not be evaluated if Condition 1 is false.
However it then asks
"Can you spot the run-time error that might occur if short-circuit evaluation wasn't in use in the line:
WHILE pointer < LengthOfList AND list[pointer] != searched for "
I have searched and searched for an answer and have run through the algorithm on paper with different items over and over for the past 2 weeks but I just cannot get my head round what the run time error could possibly be. Could anyone please see if they can spot this error and explain it to me? Many thanks.
I think the question needs to be reevaluated here. First, let's define short-circuit evaluation. Short-circuit evaluation is the use of boolean operators such as &&(the AND operator) and ||(the OR operator) so that only one of two arguments have to be checked due to the result of one argument. For example consider these examples where A and B are conditions,
if(A && B)
According to short-circuit evaluation, if A is false then B will never have to be checked since the overall result of A && B is false no matter what B is and the if statement's body will be skipped.
if(A || B)
Here according to short-circuit evaluation, if A is true then B will never have to be checked since the overall result of A || B is true no matter what B is and the if statement's body is executed.
Now the question is asking what will happen if short circuit evaluation is NOT used. So the question is just asking about the errors of a differently written algorithm (note the algorithm you have written above is completely fine as it is). In essence, what errors can occur if both conditions in the while loop are checked with each iteration? Because right now, what's preventing the runtime error is that in the last iteration, only the first condition is checked to prevent an ArrayIndexOutOfBoundsException. If the last iteration of the while loop checked both conditions, then a runtime error would occur because the program is trying to access an element that is outside the bounds of the array.