Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Binary search algorithm

  1. Jul 9, 2011 #1
    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)
    Code (Text):
    PROCEDURE BinarySearch (A         : anArray,
                            Size      : anArraySize,
                            Key       : INTEGER,
                            VAR Found : BOOLEAN;
                            VAR Index : anArrayIndex);
    Var Low, High : anArrayIndex;
       LOW := 1;
       High := Size;

          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)
    has the pitfall that when the final iteration starts with Low=High, then it will return
    Code (Text):
    even if the Key is not found in the array.

    I've tried with the following example and didn't find a mistake:
    Since 2<3, Key < A[index] and
    Since Low>High, the loop is terminated
    Low<=High isn't true so FOUND is set to false, which is a correct answer.
  2. jcsd
  3. Jul 9, 2011 #2
    I have noticed that when the key is 3, we have
    Key<A[1] is false, hence
    Low =Index+1=2
    Since Low>High, loop ends


    This is an example in which the algorithm fails. Am I correct?
  4. Jul 9, 2011 #3
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook