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;
    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
    Code (Text):
    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.
     
  2. jcsd
  3. Jul 9, 2011 #2
    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?
     
  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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Binary search algorithm
  1. Binary search help (Replies: 1)

  2. Binary Search Tree C++ (Replies: 1)

  3. Binary Search Error (Replies: 0)

Loading...