- #1
dalcde
- 166
- 0
On the website http://stackoverflow.com/questions/504335/what-are-the-pitfalls-in-implementing-binary-search, it states that the Pascal code (note that in Pascal, the array indexing starts with 1)
has the pitfall that when the final iteration starts with Low=High, then it will return
even if the Key is not found in the array.
I've tried with the following example and didn't find a mistake:
A=[3]
Key=2
Low=1
High=1
Index=1
Since 2<3, Key < A[index] and
High=Index-1=0
Since Low>High, the loop is terminated
Low<=High isn't true so FOUND is set to false, which is a correct answer.
Code:
PROCEDURE BinarySearch (A : anArray,
Size : anArraySize,
Key : INTEGER,
VAR Found : BOOLEAN;
VAR Index : anArrayIndex);
Var Low, High : anArrayIndex;
BEGIN
LOW := 1;
High := Size;
REPEAT
Index := (Low + High) DIV 2;
If Key < A[Index]
THEN High := Index - 1
ELSE Low := Index + 1
UNTIL (Low > High) OR (Key = A[Index]);
FOUND := (Low <= High)
END;
Code:
FOUND=true
I've tried with the following example and didn't find a mistake:
A=[3]
Key=2
Low=1
High=1
Index=1
Since 2<3, Key < A[index] and
High=Index-1=0
Since Low>High, the loop is terminated
Low<=High isn't true so FOUND is set to false, which is a correct answer.