CODEWITHSUNDEEP
javaarrays
EhhChris
EhhChris

Reputation: 25

Check if an int is between two items in an array

Alright, so I'm working on a leveling system in java. I have this from my previous question for defining the level "exp" requirements:

    int[] levels = new int[100];
    for (int i = 1; i < 100; i++) {
        levels[i] = (int) (levels[i-1] * 1.1);
    }

Now, my question is how would I determine if an exp level is between two different integers in the array, and then return the lower of the two? I've found something close, but not quite what I'm looking for here where it says binary search. Once I find which value the exp falls between I'll be able to determine a user's level. Or, if anyone else has a better idea, please don't hesitate to mention it. Please excuse my possible nooby mistakes, I'm new to Java. Thanks in advance to any answers.

Solved, thanks for all the wonderful answers.

Upvotes: 2

Views: 90

Answers (4)

rgettman
rgettman

Reputation: 178263

With a general sorted array of numbers, binary search is the way to go, which is O(log n). But because there is a mathematical relationship between the numbers (each number is 1.1 times the previous one), take advantage of that fact. You're looking for the maximum exponent level such that

levels[0] * Math.pow(1.1, level) <= exp

Solving for level,

level = log{base 1.1}(exp / levels[0])

Taking advantage of the fact that loga(b) = ln(b) / ln(a)...

int level = (int) Math.log(exp/levels[0]) / Math.log(1.1);

Because of the mathematical relationship, you just need this calculation, and no searching, so it's O(1).

double base = 1;
double factor = 1.1;

for (double score : Arrays.asList(1.0, 1.1, 1.3, 8.6, 9.46))
{
   int level = (int) (Math.log(score / base) / Math.log(factor));
   System.out.println(level);
}

Prints

0
1
2
22
23

Upvotes: 1

jeremyjjbrown
jeremyjjbrown

Reputation: 8009

Why not just use the Arrays Class?

int valueToFind = 100;
int index = Arrays.binarySearch(levels, valueToFind)

Upvotes: 0

Ted Hopp
Ted Hopp

Reputation: 234807

You can use the built-in binary search method:

int exp = . . .
int pos = Arrays.binarySearch(levels, exp);
if (pos < 0) {
    // no exact match -- change pos to the insertion index
    pos = -pos - 1;
    // Now exp is between levels[pos] and levels[pos - 1]
    // (or less than levels[0] if pos is now 0)
} else {
    // exp is exactly equal to levels[pos]
}

Upvotes: 1

peter.petrov
peter.petrov

Reputation: 39457

Yes, you should do binary search here as your array elements seem to be sorted.
This follows from the way you initialize them.
You can also do linear search of course but the former is better.

Upvotes: 0

Related Questions