PDAS home > Contents > Standard Atmosphere > Binary Search
Public Domain Aeronautical Software (PDAS)  

How do you find your place in an ordered table?

If we have an ordered table x1, x2, ... , xn and a given value u, then the goal is to find the unique index i such that xi <= u < xi+1. It is always distressing to read programs that search each interval sequentially until a match is found.

  sequential:                         bisection:

  DO j=2,n                             i=1   
    IF (u < x(j)) THEN                 j=n 
      i=j-1                            DO 
      EXIT                               k=(i+j)/2   
    END IF                               IF (u < x(k)) THEN 
  END DO                                   j=k  
                                         ELSE
                                           i=k
                                         END IF
                                         IF (i+1 >= j) EXIT
                                       END DO

It may have a few more lines, but the number of comparisons needed to exit the loop can be dramatically smaller, especially for large tables. You can read a more thorough description in Numerical Recipes, section 3.4. or in Knuth's Sorting and Searching.

If you are writing a general routine, then you have to deal with such problems as u being outside the range, or if the table turns out to be not sorted.

PDAS home > Contents > Standard Atmosphere > Binary Search
Public Domain Aeronautical Software (PDAS)