find closest array value to a number

[nozom]

Afternoon all 🙂

I have an array ~

$thearray=array(10,34,65,76,.....);

I then have a variable,

$var=14;

I would like to find the number in the array that is closest to 14. hopefully this will pull out 10.

Any ideas on how to code that, i'm sure its quite straight forward but i can't see it.

ta,
nozom

[laserlight]

Should be quite simple, but I dont think PHP has a function for it.

Could try:

//assume that $array is an array
function getClosestElement($array, $value) {
	$size = count($array);
	if ($size > 0) {
		//absolute difference between 0th element and input value
		$diff = abs($array[0] - $value);
		//element closest to input value
		$ret = $array[0];
		//loop through the rest of the array
		for ($i = 1; $i < $size; $i++) {
			$temp = abs($array[$i] - $value);
			if ($temp < $diff) {
				//set new difference and closest element
				$diff = $temp;
				$ret = $array[$i];
			}
		}
		return $ret;
	} else {
		return NULL;
	}
}

[bubblenut]

Well, is the array sorted? If not the sort it with [man]sort()[/man] then you have a couple of options. A straight iteration through the array which will, on average require O(n/2) comparisons before you find the first result above the criteria (and from there it's a one step operation to find the nearest). The alternative is to implement a binary search on the array which will require O(log2n) comparisons I believe. This will be much quicker on average but is a little more complex to implement (not much though).

Straight Iteration

$crit=10;
sort($array);
for($i=0;$i<count($array);$i++) {
  if($crit>$array[$i]) {
    if(($array[$i]-$array)>($array-$array[$i-1])) {
      $closest=$array[$i-1];
    } else {
      $closest=$array[$i];
    }
  }
}
echo($closest);

Binary Search

$crit=10;
sort($array);

echo(binarySearch($array, $crit, 0, count($right)));

function binarySearch($array, $crit, $left, $right) {
  if($right>$left) {
    if($array[$right]-$crit>$crit-$array[$left]) {
      return $array[$left];
    } else {
      return $array[$right];
    }
  } else {
    $mid=floor(($left+$right)/2);
    if($array[$mid]==$crit) {
      return $crit;
    } elseif($crit<$array[$mid]) {
      return binarySearch($array, $crit, $left, $mid-1);
    } else {
      return binarySearch($array, $crit, $mid+1, $right);
    }
  }
}  

Hope This Helps

Dunno about you but I reckon that's a pretty good 999th post 😃

Bubble

[laserlight]

If you do use sort() then there's no point in using a sequential search, since you've just wasted time sorting.
You might as well use a binary search.
But a sequential search will generally be faster than a sort followed by a binary search.

[nozom]

Cheers for those guys

I was looking at the iteration version myself, the binary one looks very interesting as well. will try now

Congrats on your 999th post, i've only posted 100 or so and i've been on here a year longer, hows that for bad form eh.

cheers,
nozom

[nozom]

I used your first version bubblenut, no need to sort as the array has already been sorted.

I had to change a few things as your version had a few errors but here the result.

for($i=0;$i<count($thechars);$i++) 
	{ 
	if($splitat>$thechars[$i]) 
		{ 
		if (($thechars[$i]-$splitat)>($splitat-$thechars[$i])) 
			{ 
			$closest=$thechars[$i]-1; 
			} 
		else 
			{ 
			$closest=$thechars[$i]; 
			}
		} 
	} 
$splitat=$closest;

I'm using it to find the correct breakpoints so that i only insert an image on a new line, rather than half way through a sentance.

Appreciate the excellent help,
nozom

[laserlight]

Have you tried my version?

I'm using it to find the correct breakpoints so that i only insert an image on a new line, rather than half way through a sentance.

You're using it on a string?

[nozom]

Didn't try your one laserlight, used bubblenuts first and it did the job.

What i'm doing is running through a string taking note of where line breaks occur and noting the character number after the line break.

My content management system allows for images to be placed a percentage distance down the page (i.e. place image 50% down the page)

If the image has been designated that it be on a line by itself(rather than having text wrapping around it) then i can't stick it in the middle of a sentance, it has to be after a line break.

I work out what character number is 50% of the way down the page (say position 302), then work out the closest linebreak, and put it in there.

hope that makes sense,
nozom

[bubblenut]

Originally posted by laserlight
If you do use sort() then there's no point in using a sequential search, since you've just wasted time sorting.
You might as well use a binary search.
But a sequential search will generally be faster than a sort followed by a binary search.

Ah, yes, I forgot th break :o it should be.

$crit=10;
sort($array);
for($i=0;$i<count($array);$i++) {
  if($crit>$array[$i]) {
    if(($array[$i]-$array)>($array-$array[$i-1])) {
      $closest=$array[$i-1];
    } else {
      $closest=$array[$i];
    }
    break;
  }
}
echo($closest);

With the break it's O(n/2) (on average) plus however long it takes to do the sort whereas your version is O(n) so it depends on how long the sort takes, I was assuming it was going to be pretty damned quick but then I guess so's a loop with only one condition, one function call and a couple of assignments. I'm not sure which is quicker but I'm just about to test all three.

[bubblenut]

Right well, laserlight, I guess you win seeing as neither of mine actually worked as they were shown :o :o
However once I'd got mine working the results were as follows.

Array of 1000 elements between 10000 and 99999.

Laserlight : Consistently around the 0.0064 mark

Bubble 1 : Between 0.004 and 0.008 (but averaging about 0.007)

Bubble 2 : around the 0.004 - 0.006 mark

Bubble