What are the pitfalls in implementing binary search?

[dalcde]

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)

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;

has the pitfall that when the final iteration starts with Low=High, then it will return

FOUND=true

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.

 

[dalcde]

I have noticed that when the key is 3, we have
Key=3
Low=1
High=1
Index=1
Key<A[1] is false, hence
Low =Index+1=2
Since Low>High, loop ends

FOUND=(Low<=High)=False

This is an example in which the algorithm fails. Am I correct?

 

[aegrisomnia]

There's a lot wrong with this and it's clear either (a) an engineer/scientist/mathematician wrote this without a clue or (b) this is an exercise devised by a computer scientist. Either way...

Trivially, the pitfall they mention does not hold and the problem you found does hold. If the loop body ever executes with low = high, the condition will fail (since either low is incremented or high is decremented) and high < low holds. So whenever the loop gets to the point where low = high, the algorithm will return false, regardless of whether the element at the position index = low = high is the target or not.

There are two methods to fix this. Note that the problem only exists where there is an element in the array that matches the target and we happen to test it at the very last possible iteration of the loop. So...
Method #1: Change "ELSE LOW := INDEX + 1" to "IF key > A[index] THEN LOW := INDEX + 1".
Method #2: Change "FOUND = (LOW <= HIGH)" to "FOUND = (key = A[index])".

Let me know if I goofed.