2020-04-30-PHP 实现搜索插入位置

layout: posttitle: PHP 实现搜索插入位置
subtitle: PHP 实现搜索插入位置
date: 2020-04-30
author: he xiaodong
header-img: img/default-post-bg.jpg
catalog: true
tags:
- Go
- PHP
- LeetCode
- 搜索插入位置

题干

给定一个非负整数数组 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

最后恰饭 阿里云全系列产品/短信包特惠购买 中小企业上云最佳选择 阿里云内部优惠券