<?php
/*
1
/ \
2 3
/ \ \
4 5 6
\
7
*/
$a = ['d'=>1, 'l'=>&$b, 'r'=>&$c];
$b = ['d'=>2, 'l'=>&$d, 'r'=>&$e];
$c = ['d'=>3, 'l'=>null, 'r'=>&$f];
$d = ['d'=>4, 'l'=>null, 'r'=>&$g];
$e = ['d'=>5, 'l'=>null, 'r'=>null];
$f = ['d'=>6, 'l'=>null, 'r'=>null];
$g = ['d'=>7, 'l'=>null, 'r'=>null];
bfs($a);
echo "\n";
dfs($a);
echo "\n";
function bfs($t) {
$queue = [$t];
while ($queue) {
$node = array_shift($queue);
echo $node['d'];
if (is_array($node['l'])) {
array_push($queue, $node['l']);
}
if (is_array($node['r'])) {
array_push($queue, $node['r']);
}
}
}
function dfs($t) {
$stack = [$t];
while ($stack) {
$node = array_pop($stack);
echo $node['d'];
if (is_array($node['r'])) {
array_push($stack, $node['r']);
}
if (is_array($node['l'])) {
array_push($stack, $node['l']);
}
}
}
$a = [5,1,2,8,3,4,1];
qsort($a);
var_dump($a);
function qsort(&$arr, $l = 0, $h = null) {
if (is_null($h)) $h = count($arr) - 1;
if ($l >= $h) return;
$v = $arr[$l];
$i = $l;
$j = $h;
while ($i < $j) {
while ($arr[$j] >= $v && $i < $j) {
$j--;
}
while ($arr[$i] <= $v && $i < $j) {
$i++;
}
if ($i == $j) {
$arr[$l] = $arr[$i];
$arr[$i] = $v;
break;
}
$tmp = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $tmp;
}
qsort($arr, $l, $i - 1);
qsort($arr, $i + 1, $h);
}
var_dump(binsearch($a, 0));
var_dump(binsearch($a, 1));
var_dump(binsearch($a, 6));
var_dump(binsearch($a, 8));
var_dump(binsearch($a, 9));
function binsearch($arr, $val) {
$l = 0;
$h = count($arr) - 1;
while ($l <= $h) {
$m = intval(($l + $h) / 2);
if ($arr[$m] == $val) {
return $m;
}
if ($arr[$m] < $val) {
$l = $m + 1;
} else {
$h = $m - 1;
}
}
return -1;
}
- Output for 5.6.0 - 5.6.40, 7.0.0 - 7.0.33, 7.1.0 - 7.1.33, 7.2.0 - 7.2.33, 7.3.0 - 7.3.33, 7.4.0 - 7.4.33, 8.0.0 - 8.0.30, 8.1.0 - 8.1.28, 8.2.0 - 8.2.18, 8.3.0 - 8.3.4, 8.3.6
- 1234567
1247536
array(7) {
[0]=>
int(1)
[1]=>
int(1)
[2]=>
int(2)
[3]=>
int(3)
[4]=>
int(4)
[5]=>
int(5)
[6]=>
int(8)
}
int(-1)
int(1)
int(-1)
int(6)
int(-1)
- Output for 8.3.5
- Warning: PHP Startup: Unable to load dynamic library 'sodium.so' (tried: /usr/lib/php/8.3.5/modules/sodium.so (libsodium.so.23: cannot open shared object file: No such file or directory), /usr/lib/php/8.3.5/modules/sodium.so.so (/usr/lib/php/8.3.5/modules/sodium.so.so: cannot open shared object file: No such file or directory)) in Unknown on line 0
1234567
1247536
array(7) {
[0]=>
int(1)
[1]=>
int(1)
[2]=>
int(2)
[3]=>
int(3)
[4]=>
int(4)
[5]=>
int(5)
[6]=>
int(8)
}
int(-1)
int(1)
int(-1)
int(6)
int(-1)
preferences:
203.98 ms | 402 KiB | 288 Q