[SOLVED] efficient way to search in arrays

[SirChick]

I have an array of about 99 numbers in a list which are comma seperated... and currently im just getting a $var and using a while loop to check through the array to see if its in the array or not.

 

Now with 99 numbers and if the $var was 98 ... it has to while loop 98 times till it finds it, which is going to be a bit of power hogger if im looking through many numbers.

 

Is there any array search function so that itll find the first then second digit of a $var? That would limit it to max of 20 checks because it only needs to search 0 to 9 and then 0 to 9 again.

 

If so what function can do this?

[xtopolis]

You are describing a binary search algorithm.

 

A quick search returned something like this: http://us.php.net/manual/en/function.array-search.php#89413

 

You could build your own, or index/store your data differently.

[corbin]

100 numbers wouldn't be worth coming up with an indexing system.

 

 

You could just use in_array, but it does exactly what you said you don't want it to do (the whole looping thing... lol).

[Maq]

I have an array of about 99 numbers in a list which are comma seperated... and currently im just getting a $var and using a while loop to check through the array to see if its in the array or not.

 

If your ultimate goal is to see if the number is in the array you can just use in_array().

 

Is there any array search function so that itll find the first then second digit of a $var?

 

Not really sure what that means...  You can get the first and second digit of $var by doing:

 

$var = "98";
echo "First Digit: " . $var[0];
echo "
Second Digit: " . $var[1];
?>

 

Hope this helps.

[SirChick]

100 numbers wouldn't be worth coming up with an indexing system.

 

Thanks for the replies everyone. And I agree with out Corbin, though in due course the total numbers involved will reach the thousands over time so its better i plan ahead for efficientcy.. so sounds like binary search algorithm is needed i'll do some searching on it!

[corbin]

The only problem with a binary search is that the values need to be ordered.  Will the values be in order already?  If not, it would be less intense to just loop through the array than sort it most likely ;p.  (Sorting for people is easy and quick, but sorting for computers is a bit different.)

[SirChick]

Damn it might not be in order. Is it quite heavy processing to order the numbers aswell ?

[corbin]

<?php

$numbers = range(0, 100);
//Shuffle it so it's not in order ;p
shuffle($numbers);

$orig_numbers = $numbers;

$START = microtime(true);

for($i = 0; $i < 10000; ++$i) {
sort($numbers);
shuffle($numbers);
}

$END = microtime(true);

echo ($END - $START) . PHP_EOL;


$START = microtime(true);

for($i = 0; $i < 10000; ++$i) {
in_array(rand(50, 150), $orig_numbers);
shuffle($numbers);
}

$END = microtime(true);

echo ($END - $START) . PHP_EOL;

 

Output:

 

0.51721501350403

0.13445687294006

 

 

So, it takes about 1/4 the time to just do in_array in that little script.  Note that an extra rand() call is in the in_array block too.

 

But, that is flawed since it doesn't explore how well the set would scale.

 

 

But I would imagine that in_array will always beat sort(), and that's before you even do the binary tree stuff ;p.

[SirChick]

Thanks for the info dude