SEARCH IN ASSOCIATIVE ARRAYS

PROBLEM
Given an array A.1,...,A.N of any distinct elements and target value V. Search routine should return an index of V in A. if V is present in the array, and N+1 otherwise.

ALGORITHM
By use of key comparisons alone, it is impossible to complete a search of N items in fewer than lg N comparisons on average. In the Rexx language we would simply store values A.1,...,A.N in an associative array and use the V value as index of associative array to locate the index of V in the A. array.

IMPLEMENTATION
Unit: program
 
Parameter: a positive integer N
 
Notes: Elements of the array A. are given from keyboard. In next phase user enters the target values V from keyboard. Program displays the index of the V value in the A. array or N+1 when the V value is not present in the array. Program ends when the target value is %

 

parse arg N
AA. = N + 1
say "Create the A. array"
do J = 1 to N
  say J". element?"
  parse linein A.J; Aj = A.J; AA.Aj = J
end
do forever
  say "Enter a target value"
  parse linein V
  if V = "%" then exit
  say "Index of" V "in A. array is" AA.V
end

 

 

CONNECTIONS


Cover Contents Index Main page

last modified 30th July 2001
Copyright 2000-2001 Vladimir Zabrodsky
Czech Republic