Re: recursive binary search

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