0

I'm looking for an efficient way to map a N integers to [1,N].

The N integers are actually entries of a sorted array A with no redundancies, and my goal is to be able to simply access the index of every entry of the array.

Example :

For a given array A of integers, sorted and without redundancies, but with gaps and possibly very large numbers (you could have 1000 integers ranging from 25 to 10^6), I need a way of finding the index of every entry in an efficient way. For example if A[15] = 1546, I need to be able to do index(1546) = 15. My problem is that I need to do this in Fortran, and as far as I know, there are no real hash table libraries.

Dooggy
  • 330
  • 2
  • 11
  • For a sorted array with no redundancies (for example A = [2,4,7,23]), I want to be able to access the index of every entry (i.e. A_inverse(7) = 3.). I don't really have a code to show as it is more of a general problem. It just so happens that I need to do this in Fortran. – Dooggy Sep 01 '15 at 22:57
  • This problem is precisely solved by a hash table, unless the range of possible values is small enough that you can create an inverted lookup table. – rici Sep 01 '15 at 23:18

1 Answers1

1

I think, you can use a binary search for solve your problem. It is simple for code.

Look this page [Binary search in array issue using Fortran

Using binary search you get the inverse index of the given number.

Community
  • 1
  • 1
Tiago
  • 26
  • 2