PHP 实现二分查找的四个案例

案例一

• 介绍

在一组数字类型的有序数组中，查询某个数字的数组下标。

• 图解

• 创建 simple1.php 内容如下：

<?php 
function main($arr, $targetNumb){
	$middle = $low = 0;
	$high = count($arr)-1;
	$isfind = 0;
	while (true) {
		if ($low <= $high) {
			$middle = floor(($high+$low)/2);
			echo $middle.PHP_EOL;
			if ($arr[$middle]==$targetNumb) {
				echo $targetNumb.'在数组中，下标值为:'.$middle;
				$isfind = 1;
				break;
			} elseif ($arr[$middle]>$targetNumb) {
				// 说明该数在low-middle之间
				$high = $middle-1;
			} else {
				// 说明该数在middle-high之间
				$low = $middle+1;
			}
		}
	}
	if ($isfind==0) {
		echo '数组不含'.$targetNumb;
	}
}
// 需要查找的数字
$targetNumb = 8;
// 目标有序数组
$arr = [1,2,3,4,5,6,7,8,9];
main($arr, $targetNumb);

• 执行

$ php simple1.php
8 在数组中，下标值为：7

案例二

• 介绍

在一组经过任意位数的旋转后的数字类型的有序数组中，查询某个数字的数组下标。

• 图解

• 创建 simple2.php 内容如下：

<?php 
function main($arr,$target,$begin,$end){
	if ($begin == $end) {
		if ($target == $arr[$begin]) {
			return $begin;
		} else {
			return false;
		}
	}
	$middle = ceil(($begin+$end)/2); 
	if ($target == $arr[$middle]) {
		return $middle;
	}
	if ($arr[$begin]<=$arr[$middle-1]) {
		if ($arr[$begin]<=$target && $target<=$arr[$middle-1]) {
			return main($arr,$target,$begin,$middle-1);
		} else {
			return main($arr,$target,$middle+1,$end);
		}
	} else {
		if ($arr[$middle+1]<=$target && $target<=$arr[$end]) {

			return main($arr,$target,$middle+1,$end);
		} else {

			return main($arr,$target,$begin,$middle-1);
		}
	}
}
// 需要查找的数字
$target = 8;
// 目标旋转后的有序数组
$arr = [5,6,7,8,9,1,2,3,4];
$begin = 0;
$end = count($arr)-1;
$targetKey = main($arr,$target,$begin,$end);
echo '原始数组：'.json_encode($arr).PHP_EOL;
if ($targetKey) {
	echo $target.'在数组中，下标值为：'.$targetKey;
} else {
	echo '数组不含'.$target;
}

• 执行

$ php simple2.php
原始数组：[5,6,7,8,9,1,2,3,4]
8在数组中，下标值为：3%

案例三

• 介绍

在一组数字类型的数组中，查询是否存在大于某个数字的数组元素。

• 图解

• 创建 simple3.php 内容如下：

<?php
function main($arr,$target){
	$middle = $low = 0;
	$high = count($arr)-1;
	$isfind = 0;
	while (true) {
		if ($low<=$high) {
			$middle = floor(($high+$low)/2);
			echo $middle;
			if ($arr[$middle]>$target && ($middle==0 || $arr[$middle-1] <= $target)) {
				echo "第一个比".$target."大的数字是".$arr[$middle];
				$isfind = 1;
				break;
			} elseif ($arr[$middle] > $target) {
				// 说明该数在low-middle之间
				$high = $middle-1;
			} else {
				// 说明该数在middle-high之间
				$low = $middle+1;
			}
		}
	}
	if ($isfind==0) {
		echo "数组不含大于".$target."的数字";
	}
}
$target = 9;
$arr = [-1,3,3,7,10,14,14];
main($arr,$target);

• 执行

$ php simple3.php
第一个比 9 大的数字是 10

案例四

• 介绍

查找两个有序数组合并后的中位数。

• 创建 simple4.php 内容如下：

<?php
function main($a,$begina,$enda,$b,$beginb,$endb){
	if ($enda-$begina==0) {
		if ($a[$beginb]>$b[$beginb]) {
			return $b[$beginb];
		} else {
			return $a[$beginb];
		}
	}
	if ($enda-$begina==1) {
		if ($a[$begina]<$b[$beginb]) {
            if ($b[$beginb]>$a[$enda]) {
                return $a[$enda];
            } else {
                return $a[$beginb];
            }
        } else {
            if ($b[$beginb]<$a[$enda]) {
                return $a[$begina];
            } else {
                return $a[$endb];
            }
        }
	}
	if ($endb-$beginb<2) {
        if (($endb-$beginb == 0) && (($enda-$begina)%2 != 0)) {
            $m = $a[$beginb];
            $bb = $b[floor(($enda+$begina)/2)-1];
            $c = $b[floor(($enda+$begina)/2)];
            if ($m<$bb) {
                return $bb;
            } elseif ($m<$c) {
                return $m;
            } else {
                return $c;
            }
        } elseif (($endb-$beginb == 0) && (($enda-$begina)%2 == 0)) {
            $m = $a[$beginb];
            $c = $b[floor(($enda+$begina)/2)];
            $d = $b[floor(($enda+$begina)/2)+1];
            if ($m<$c) {
                return $c;
            } elseif ($m<$d) {
                return $m;
            } else {
                return $d;
            }
        } else {
            $m = $b[$beginb];
            $n = $b[$endb];
            $bb = $a[floor(($enda+$begina)/2)-1];
            $c = $a[floor(($enda+$begina)/2)];
            $d = $a[floor(($enda+$begina)/2)+1];
            if ($n<$bb) {
                return $bb;
            } elseif ($n>$bb && $n<$c) {
                return $n;
            } elseif ($n>$c && $n<$d) {
                if ($m>$c) {
                    return $m;
                } else {
                    return $c;
                }
            } else {
                if ($m<$c) {
                    return $c;
                } elseif ($m<$d) {
                    return $m;
                } else {
                    return $d;
                }
            }
        }
    } else {
        $mida = floor(($enda+$begina)/2);
        $midb = floor(($endb+$beginb)/2);
        if ($a[$mida]<$b[$midb]) {
            $step = $endb-$midb;
            return main($a, $begina+$step, $enda, $b, $beginb, $endb-$step);
        } else {
            $step = $midb-$beginb;
            return main($a, $begina, $enda-$step, $b, $beginb+$step, $endb);
        }
    }

}
$arr1 = [1,2,3,4,5,6];
$arr2 = [7,8,9];
echo main($arr1, 0, count($arr1)-1, $arr2, 0, count($arr2)-1);

• 执行

$ php simple4.php
5