PHP 实现搜索插入位置

PHP 实现搜索插入位置

author: he xiaodong date: 2020-04-30
题干

给定一个非负整数数组 A,返回一个数组,在该数组中, A 的所有偶数元素之后跟着所有奇数元素。

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5
输出: 2

示例 2:

输入: [1,3,5,6], 2
输出: 1

示例 3:

输入: [1,3,5,6], 7
输出: 4

示例 4:

输入: [1,3,5,6], 0
输出: 0

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/search-insert-position

既然是有序数组,那就尽量少的遍历,多用判断来搞定,这样会比较快

PHP 实现

function searchInsert($nums, $target) {
    $count = count($nums);
    for ($i = 0; $i < $count; $i++) {
        if (isset($nums[$i + 1]) && $nums[$i] < $target && $target <= $nums[$i +1]) {
            return $i + 1;
        }

        if (!isset($nums[$i + 1]) && $nums[$i] < $target) {
            return $i + 1;
        }

        if ($nums[$i] >= $target) {
            return 0;
        }
    }
}

return searchInsert([1,3,5,6], 5); // output: 2
二分法解题思路

一般使用 二分查找 都需要先对原数组进行排序,题中给到的数组是已经排序的,因此这一步可以省去。

二分查找 思路比较简单,首先初始化三个指针: left 指向 nums 最左边的元素,right 指向 nums 右边的元素,根据 left 和 right 计算 mid 指针。我们先拿目标值 target 与 nums [mid] 进行比较。

如果 target > nums[mid],说明要查找的值有可能在 nums[mid+1, right] 之间,这时候将 left 赋值为 mid + 1,right 不变,重新计算一下 mid,重新比较。

如果 target < nums[mid],说明要查找的值有可能在 nums[left, mid-1] 之间,这时候将 right 赋值为 mid - 1,left 不变,重新计算一下 mid,重新比较。

如果 target == nums[mid],那么恭喜找到啦,根据题意,找到的索引值就是 target 插入的目标位置,即返回 mid 即可。

如果 二分查找 结束仍是没有找到 target 的值,最后返回 left 就可以了,至于为什么 left 的值是 target 插入的位置,可以看流程图的分析。

mid 的计算方式: mid = left + (rigth - left) / 2,至于为什么不用 ( left + right ) / 2 来计算 mid 是因为 right + left 有可能溢出。 注: (right - left) / 2 取整,因为数组的索引值是整数。

———————————————— 原文作者:三斤和他的喵 转自链接:https://learnku.com/articles/43723#reply139614

PHP 实现V2 二分法查找

function searchInsert($nums, $target) :int {
    if (count($nums) <= 0) {
        return 0;
    }

    $left = 0;
    $right = count($nums) - 1;
    while ($left <= $right) {
        // 根据 left 和 right 计算 mid 的值
        $mid = $left + ($right - $left) / 2; // ( left + right ) / 2

        // 目标值大于中间值,left = mid + 1
        if ($nums[$mid] < $target) {
            $left = $mid + 1;

        // 目标值小于中间值 right = mid - 1
        } else if ($nums[$mid] > $target) {
            $right = $mid - 1;
        } else {
            // 目标值等于中间值返回 mid,即为目标值需要插入的位置
            return $mid;
        }
    }

    // 找不到目标值,这时候返回left就是目标值需要插入的位置
    return $left;
}

return searchInsert([1,4,5,7], 3);  // output:1