Re: recursive binary search

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 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