Re: recursive binary search

On Thu, 17 Aug 2000, Mike Wallace wrote: > Thanks, you're right. I also noticed that the recursive function calls need to > be returned: > > } else if ($array[$mid]["date"] > $finddate) { > return bin_search($array, $low, $mid-1, $finddate); > ^^^^^^ > } else if ($array[$mid]["date"] < $finddate) { > return bin_search($array, $mid+1, $high, $finddate); > ^^^^^^ > I got this working but had to re-write from scratch to see the problems. > > Mike Ah yes, of course. I have written an n-ary tree implementation of a site tree at < http://www.apt7.com/src/classes/SiteTree.phpc >; and of course, when you're dealing with a tree, you have to deal with recursion all over the place. Should've known you'd have to return stuff. Dean. > > > Dean Hall wrote: > > > On Thu, 17 Aug 2000, Mike Wallace wrote: > > > > > I'm attempting to code a recursive binary search, but am having trouble. > > > It's possible that I'm doing something fundamentally wrong here with > > > passing parameters to a recursive function. More likely, there's > > > something simple that I'll kick myself for posting, but darned if I can > > > see the problem. > > > > > > // Start by initializing an my array of associative arrays. > > > $i=0; > > > for ($date = 20000801; $date <= 20000815; $date++) { > > > $myarray[$i] = array ( > > > "date" => $date, > > > "index" => $i > > > ); > > > $i++; > > > } > > > > > > // Search $array for $finddate. $low is first element (0) and > > > // $high is last element (count($array) - 1). > > > function bin_search( &$array, $low, $high, $finddate ) { > > > echo "\$low = " . $low . "<BR>"; > > > echo "\$high = " . $high . "<BR>"; > > > echo "\$finddate = " . $finddate . "<BR>"; > > > echo "\$array[1][\"date\"] = " . $array[1]["date"] . > > > "<BR>"; > > > > > > if ($low > $high) { > > > return -1; // no match > > > } > > > $mid = floor((high + low)/2); > > > if ($array[$mid]["date"] = $finddate) { // match > > > > Make sure you use '==' to compare. I think '=' is always the > > assignment > > operator, just like in C++. '==' is the equality-comparison operator. > > > > > return $mid; > > > } else if ($array[$mid]["date"] > $finddate) { > > > bin_search($array, $low, $mid-1, $finddate); > > > } else if ($array[$mid]["date"] < $finddate) { > > > bin_search($array, $mid+1, $high, $finddate); > > > } else { > > > return -1; > > > } > > > } > > > > > > > > > // Call the function and echo output > > > $myvar = bin_search ($myarray, 0, count($myarray)-1, 20000802); > > > echo "<P>The function returned $myvar"; > > > > > > The function is called only once (doesn't recurse), as evidenced by the > > > output: > > > > > > $low = 0 > > > $high = 14 > > > $finddate = 20000802 > > > $array[1]["date"] = 20000802 > > > > > > The function returned 0 > > > > > > > > > > > > > > > > > > > -- > > PHP General Mailing List (http://www.php.net/) > > To unsubscribe, e-mail: php-general-unsubscribe@lists.php.net > > For additional commands, e-mail: php-general-help@lists.php.net > > To contact the list administrators, e-mail: php-list-admin@lists.php.net > > >