| 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;
|
| .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.
|