题干
给定一个非负整数数组 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
最后恰饭 阿里云全系列产品/短信包特惠购买 中小企业上云最佳选择 阿里云内部优惠券
