PHPによるアルゴリズム 2分検索法
2022-08-26
2022-08-26
説明：
https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2
PHPソース：
```
<?php
/**
* 1000以内の乱数を生成する
*
* @param int $count
* @return array
*/
function createRandArray($count) {
$arr = [];
for ($i=0; $i<$count; $i++) {
$arr[] = mt_rand(1, 1000);
}
return$arr;
}
/**
* ソート
*
* @param array $arr
* @return array
*/
function basicSort($arr) {
$count = count($arr);
for ($i=0; $i<$count; $i++) {
$min = $arr[$i];
$s = $i;
for ($j=$i+1; $j<$count; $j++) {
if ($arr[$j] < $min) {
$min = $arr[$j];
$s = $j;
}
}
$t = $arr[$i];
$arr[$i] = $arr[$s];
$arr[$s] = $t;
}
return$arr;
}
/**
* 二分検索
*
* @param array $data
* @param int $search
* @return int
*/
function binary($data, $search) {
$low = 0;
$high = count($data) -1;
while ($low <= $high) {
$mid = (int)(($low + $high) / 2);
if ($data[$mid] == $search) {
return$mid;
}
if ($data[$mid] < $search) {
$low = $mid + 1;
}
else {
$high = $mid -1;
}
}
returnnull;
}
$n = 10;
$data = basicSort(CreateRandArray($n));
$key = mt_rand(0, $n-1);
$search = $data[$key];
$mid = binary($data, $search);
printf("data : \n");
var_dump($data);
print ("key: $key\n");
print ("search: $search\n");
print ("mid: $mid\n");
```
結果：
```
data :
array(10) {
[0]=>
int(197)
[1]=>
int(242)
[2]=>
int(249)
[3]=>
int(313)
[4]=>
int(602)
[5]=>
int(682)
[6]=>
int(740)
[7]=>
int(784)
[8]=>
int(789)
[9]=>
int(810)
}
key: 2
search: 249
mid: 2
```