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)(adsbygoogle = window.adsbygoogle || []).push({});

has the pitfall that when the final iteration starts with Low=High, then it will returnCode (Text):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;

even if the Key is not found in the array.Code (Text):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.

**Physics Forums - The Fusion of Science and Community**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Binary search algorithm

Loading...

Similar Threads - Binary search algorithm | Date |
---|---|

Different Node Deletion/Insertion in a Binary Search Tree | Oct 23, 2016 |

Programming Question (Python) - Boolean Binary Search | Mar 2, 2015 |

Binary Search Error | Aug 9, 2011 |

Binary search help | Feb 12, 2009 |

**Physics Forums - The Fusion of Science and Community**