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)