醉丶春风的Blog

前言

在上一篇文章中, 我实现了二分查找的基础算法, 还是不够完善, 比如要查找重复数据的第一条, 最后一条等, 上篇的算法就不能满足我们的需求了
这里就带来了4个二分查找的变形问题和一个我自己理解的向上查找的方法:

1. 查找第一个等于给定数值的元素
2. 查找最后一个等于给定数值的元素
3. 查找第一个大于等于给定数值的元素
4. 查找第一个小于等于给定数值的元素
5. 使用while向上查找第一个等于给定数值的元素

代码实现

不多说, 一切都在代码里

1.查找第一个等于给定数值的元素

/**
 * 查找第一个等于给定数值的元素
 * @param array $data 一个顺序结构的数组
 * @param int $number 要查找的数据
 * @return int 返回元素所在的下标或-1
 */
function binarySearch1($data, $number) {
    if (!is_array($data) || empty($data)) {
        return -1;
    }

    $low = 0;
    $high = count($data) - 1;

    if ($number < $data[0] || $number > $data[$high]) {
        return -1;
    }

    while ($low <= $high) {
        $mid = $low + (($high - $low) >> 1);
        if ($data[$mid] > $number) {
            $high = $mid - 1;
        } elseif ($data[$mid] < $number) {
            $low = $mid + 1;
        } else {
            if ($mid == 0) {
                return $mid;
            }
            // 如果当前mid元素等于number, 判断mid前一个元素是否也等于number, 如果也等于number, 则说明当前mid元素不是第一个number元素
            if ($data[$mid-1] != $number) {
                return $mid;
            }
            $high = $mid - 1;
        }
    }

    return -1;
}

2.查找最后一个等于给定数值的元素

/**
 * 查找最后一个等于给定数值的元素
 * @param array $data 一个顺序结构的数组
 * @param int $number 要查找的数据
 * @return int 返回元素所在的下标或-1
 */
function binarySearch2($data, $number) {
    if (!is_array($data) || empty($data)) {
        return -1;
    }

    $length = count($data);
    $low = 0;
    $high = $length - 1;

    // 给定的参数不在范围内
    if ($number < $data[0] || $number > $data[$high]) {
        return -1;
    }

    while ($low <= $high) {
        $mid = $low + (($high - $low) >> 1);
        if ($data[$mid] > $number) {
            $high = $mid - 1;
        } elseif ($data[$mid] < $number) {
            $low = $mid + 1;
        } else {
            // mid位于最后一个元素, 此时直接返回
            if ($mid == $length - 1) {
                return $mid;
            }
            // 如果当前mid元素等于number, 判断mid后一个元素是否也等于number, 如果也等于number, 则说明当前mid元素不是最后一个number元素
            if ($data[$mid+1] != $number) {
                return $mid;
            }
            $low = $mid + 1;
        }
    }

    return -1;
}

3.查找第一个大于等于给定数值的元素

/**
 * 查找第一个大于等于给定数值的元素
 * @param array $data 一个顺序结构的数组
 * @param int $number 要查找的数据
 * @return int 返回元素所在的下标或-1
 */
function binarySearch3($data, $number) {
    if (!is_array($data) || empty($data)) {
        return -1;
    }

    $low = 0;
    $high = count($data) - 1;

    // 给定的参数不在范围内
    if ($number < $data[0] || $number > $data[$high]) {
        return -1;
    }

    while ($low <= $high) {
        $mid = $low + (($high - $low) >> 1);
        // 如果mid元素大于等于给定的元素, 判断是否为第一个元素, 或者mid-1 < 给定的元素, 就说明mid是第一个大于等于给定数值的元素
        if ($data[$mid] >= $number) {
            if ($mid == 0 || $data[$mid-1] < $number) {
                return $mid;
            }
            $high = $mid - 1;
        } else {
            $low = $mid + 1;
        }
    }

    return -1;
}

4.查找第一个小于等于给定数值的元素

/**
 * 查找第一个小于等于给定数值的元素
 * @param array $data 一个顺序结构的数组
 * @param int $number 要查找的数据
 * @return int 返回元素所在的下标或-1
 */
function binarySearch4($data, $number) {
    if (!is_array($data) || empty($data)) {
        return -1;
    }
    $length = count($data);
    $low = 0;
    $high = $length - 1;

    // 给定的参数不在范围内
    if ($number < $data[0] || $number > $data[$high]) {
        return -1;
    }

    while ($low <= $high) {
        $mid = $low + (($high - $low) >> 1);
        // 如果mid元素小于等于给定的元素, 判断是否为最后一个元素, 或者mid+1 > 给定的元素, 就说明mid是第一个小于等于给定的元素
        if ($data[$mid] <= $number) {
            if ($mid == $length -1 || $data[$mid+1] > $number) {
                return $mid;
            }
            $low = $mid + 1;
        } else {
            $high = $mid - 1;
        }
    }

    return -1;
}

5.查找第一个等于给定数值的元素, 使用while循环向上查找

/**
 * 查找第一个等于给定数值的元素, 使用while循环向上查找, 适用于重复数据不多的情况
 * @param array $data 一个顺序结构的数组
 * @param int $number 要查找的数据
 * @return int 返回元素所在的下标或-1
 */
function binarySearch5($data, $number) {
    if (!is_array($data) || empty($data)) {
        return -1;
    }

    $low = 0;
    $high = count($data) - 1;

    if ($number < $data[0] || $number > $data[$high]) {
        return -1;
    }

    while ($low <= $high) {
        $mid = $low + (($high - $low) >> 1);
        if ($data[$mid] > $number) {
            $high = $mid - 1;
        } elseif ($data[$mid] < $number) {
            $low = $mid + 1;
        } else {
            if ($mid == 0) {
                return $mid;
            }
            /**
             * 查找到mid元素等于给定的元素
             * 通过while一直向上查找, 直到找到最后一个
             * 此方法有局限性, 重复的数据不能多如, [1, 2, 3, 4, 4, 4, 5, 6]
             * 如果重复的数据有10个, 100个, 1000个, 10000个, 该方法性能会急剧下降
             */
            while ($mid >= 0) {
                if ($data[$mid-1] != $number) {
                    break;
                }
                $mid --;
            }

            return $mid;
        }
    }

    return -1;
}