查找算法之重复二分查找

mac2023-05-27  5

重复二分查找,主要是在对已经排好序,且存在重复元素的数组中,获取要查找的元素第一次出现的位置,或者最后一次出现的位置,这种需求来使用。

<?php /** * 重复二分查找 * * @param string $find 要查找的值 * @param array $array 要查找的数组 * @return bool|string */ function repeatBinarySearch ($find, array $array) { // 数组开始下标 $left = 0; // 获取数组最后一个下标 $right = count($array) - 1; // 获取循环次数 $num = 0; // 循环遍历 while ($left < $right) { $num++; // 获取中间数值 $middle = (int) (($right + $left) / 2); // 判断 if ($array[$middle] > $find) { $right = $middle; } else if ($array[$middle] < $find) { $left = $middle; } else { // 假设当前元素不是第一个元素 for ($middle = $middle; $middle > $left; $middle--) { // 判断前面是否有相同的元素 if ($array[$middle - 1] != $array[$middle]) { var_dump('遍历了 ' . $num . ' 次'); // 如果没有,直接返回当前位置 return $middle; } } var_dump('遍历了 ' . $num . ' 次'); return $middle; } } var_dump('遍历了 ' . $num . ' 次'); // 未找到 return false; } // 创建一个 1 到 100 的数组 $array = [1, 3, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 10]; // 要查找 7 第一次出现的位置 $find = '7'; // 将数组乱序 $result = repeatBinarySearch($find, $array); var_dump($result);
最新回复(0)