[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

1311.0. "whow find the position of a number?" by MXOV08::CURIEL () Thu Oct 18 1990 18:19

    
    a simple question:
    
    
    which is the best algotithm to find the position of a number?
    
    I have an problem like this:
    
    1.2  1.21  3.432  456.5  1320 1320.0282  1500 2000  2030  5000.2 ......
    
    in this example the position of the number 456.5 is 4
    
    my list of number is too big.
    
    thanks in advance,
    
    alberto.
    
T.RTitleUserPersonal
Name
DateLines
1311.1bisection searchEAGLE1::BESTR D Best, sys arch, I/OThu Oct 18 1990 19:4128
From your example, I would guess that the array is sorted, that the input is
some number guaranteed to be in the array or between two values of the
array, and that the output is to be the index of the number.

bisection search is a common way.

Here is a lifted bisection search fragment.  No warranties express or implied.
------------------------------------------------------------------------------
(* Stolen from 'Scientific Pascal', Harley Flanders, Reston Publishing Co. *)
(* returns loc such that  x[ 1 ] <= loc < x[ n ] *)

const	n = 1000;
type	vec = array [1..n] of real;

function loc( x : vec, y : real) : integer ;

var f, m, l: integer;

begin
  f := 1;
  l := n;
  while l - f > 1 do
    begin
      m := ( f + l ) div 2;
      if y < x[ m ] then l := m else f := m
    end;
  loc := f
end;
1311.2Cross posting.CADSYS::COOPERTopher CooperThu Oct 18 1990 20:124
    This note is a cross posting from ALGORITHMS, where it is being
    actively discussed.

				    Topher
1311.3<thanks, >MXOV08::CURIELThu Oct 18 1990 22:561
    
1311.4No warranties express or impliedTRACE::GILBERTOwnership ObligatesFri Oct 19 1990 13:4918
.1> (* returns loc such that  x[ 1 ] <= loc < x[ n ] *)

What???  Shouldn't this be:

  (* returns loc such that  x[ loc ] <= y < x[ loc+1 ] *)

Actually, a better specification would be:

  (* given array x[1],...,x[n], with x[1]<...<x[n], and x[1] <= y < x[n], *)
  (* this function returns loc such that x[loc] <= y < x[loc+1]           *)

But the "x[1]<...<x[n]" condition is irrelevant!  So we make this:

  (* given array x[1],...,x[n], with x[1] <= y < x[n],                    *)
  (* this function returns loc such that x[loc] <= y < x[loc+1]           *)

FWIW, if x[n] <= y, it either returns loc s.t. x[loc]<=y<x[loc+1], or n-1.
If y < x[1], the algorithm either returns loc s.t. x[loc]<=y<x[loc+1], or 1.