note 24040 added to function.array-search

The following function I created should have 15 lines of code from the first if to the last return (lines 1-2,6,8-12 start with if). Csaba Gabor function InsertPt ($ar, $val, $searchType=0, $startPos=0, $endPos=null) { // Finds the position where $val should be array_spliced into // subarray $ar[$startPos ... $endPos] to maintain the // sortedness of $ar (which entire array is assumed either // ascending or descending). // This position is unique unless $val equals an $ar element: // // In this case the insertion point is such that // insertion of $val would happen between the first // encountered $val in the subarray and the element // just prior to that, where the search is STARTING from // the smallest (!$searchType is true) or // largest (!!$searchType is true) side of the array // // $startPos, $endPos are restricted to // [-sizeof($ar),sizeof($ar)-1] and are interchangeable // UNLESS all elements are identical in which case it // establishes the ascending order. If $ar is a singleton, // it is assumed ascending. // $endPos defaults to the end of the array // (0 if $startPos is negative, and // [the normal case] sizeof($ar)-1 otherwise). // Negative position values should be subtracted from // sizeof($ar) to get absolute position. // Logarithmic speed. Works with strings. // Adaptable to case insensitive strings (7 comparisons) // Examples with $ar = array(2, 4, 5, 5, 5, 6, 7, 10, 12) // InsertPt ($ar, 8) => 7 // InsertPt ($ar, 5) => 2 before first 5 // InsertPt ($ar, 5, 1) => 5 after the last 5 // InsertPt ($ar, -3) => 0 before the 2 // InsertPt ($ar, 12, 1) => 9 after the 12 // If $ar was reversed, the same five // functions calls would produce 2, 7, 4, 9, 0 // If $ar = [6, 6, 6, 6, 6] // InsertPt ($ar, 8) => 5 // InsertPt ($ar, 6, 1, -1, 2) => 2 // that -1 translates to 4, which implies descending order if (!$ar || $startPos<-($aSize=sizeof($ar)) || $startPos>$aSize-1) return 0; if ($endPos===null) $endPos = 0 - ($startPos>=0); // default $endPos adjustment $startPos = mod(min($aSize-1, (max (-$aSize, $startPos))),$aSize); // translate to real start pos $endPos = mod(min($aSize-1, (max (-$aSize, $endPos))), $aSize); // translate to real end pos $diff = $endPos-$startPos; if (!($dir = ($ar[0]==$ar[$aSize-1] ? 0 : ($ar[$aSize-1]<$ar[0] ? 1 : -1)))) // constant series (-1 for ascending, 1 for descending) return (($val<$ar[0] || ($val==$ar[0] && !$searchType)) ? $startPos + ($diff<0) : $endPos + !($diff<0)); if ($diff<0) { $startPos+=$endPos; $endPos=$startPos-$endPos; $startPos-=$endPos; } // make sure $startPos <= $endPos if ($val<$ar[($dir<0 ? $startPos : $endPos)]) return ($dir<0 ? $startPos : $endPos+1); // These 2 lines for when $val falls outside if ($val>$ar[($dir<0 ? $endPos : $startPos)]) return ($dir<0 ? $endPos+1 : $startPos); // series speced by $startPos, $endPos if ($val==$ar[($tmp=(($dir<0)==!$searchType)) ? $startPos : $endPos]) return ($tmp ? $startPos : $endPos+1); // if $val at sensitive endpoint if (abs($diff)==1) return $endPos; // Double series (singleton was covered in 3 prior lines) $mid = floor(($endPos+$startPos)/2); // We will halve the series $tmp = ($dir<0)==(($val==$ar[$mid]) ? !$searchType : ($val<$ar[$mid])); // Decide which half we want return InsertPt ($ar, $val, $searchType, $tmp ? $startPos : $mid, $tmp ? $mid : $endPos); } function mod($num, $base) { // returns $num modulo $base within range [0..$base-1] return ($num - $base*floor($num/$base)); } -- http://www.php.net/manual/en/function.array-search.php http://master.php.net/manage/user-notes.php?action=edit+24040 http://master.php.net/manage/user-notes.php?action=delete+24040 http://master.php.net/manage/user-notes.php?action=reject+24040