Searching a Table by Bisection

How do you find your place in an ordered table?

If we have an ordered table x₁, x₂, ... , x_n and a given value u, then the goal is to find the unique index i such that x_i <= u < x_i+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.