1.题目：https://leetcode-cn.com/problems/search-insert-position/
2.思想
（1）想法很精妙，去体会
（2）纯粹练习二分法而写
（3）二分法模板
理解二分法：https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/#comment
题目告诉你“排序数组”，其实就是在疯狂暗示你用二分查找法。
public class Solution3 {
public int searchInsert(int[] nums, int target) {
int len = nums.length;
if (nums[len - 1] return len;
}
int left = 0;
int right = len - 1;
while (left int mid = (left + right) / 2;
// 等于的情况最简单，我们应该放在第 1 个分支进行判断
if (nums[mid] == target) {
return mid;
} else if (nums[mid] // 题目要我们返回大于或者等于目标值的第 1 个数的索引
// 此时 mid 一定不是所求的左边界，
// 此时左边界更新为 mid + 1
left = mid + 1;
} else {
// 既然不会等于，此时 nums[mid] > target
// mid 也一定不是所求的右边界
// 此时右边界更新为 mid - 1
right = mid - 1;
}
}
// 注意：一定得返回左边界 left，
// 如果返回右边界 right 提交代码不会通过
// 【注意】下面我尝试说明一下理由，如果你不太理解下面我说的，那是我表达的问题
// 但我建议你不要纠结这个问题，因为我将要介绍的二分查找法模板，可以避免对返回 left 和 right 的讨论
// 理由是对于 [1,3,5,6]，target = 2，返回大于等于 target 的第 1 个数的索引，此时应该返回 1
// 在上面的 while (left // 根据题意应该返回 left，
// 如果题目要求你返回小于等于 target 的所有数里最大的那个索引值，应该返回 right
return left;
}
}
1、当把二分查找法的循环可以进行的条件写成 while (left
2、但是事实上，返回 left 是有一定道理的，如果题目换一种问法，你可能就要返回右边界 right，这句话不太理解没有关系，我也不打算讲得很清楚（在上面代码的注释中我已经解释了原因），因为实在太绕了，这不是我要说的重点。
3.代码
解法1：
class Solution {
public:
int searchInsert(vector& nums, int target) {
int length=nums.size();
for (int i=0;i {
if (nums[i]>=target)
return i;
}
return length;
}
};
解法2：
class Solution {
public:
int searchInsert(vector& nums, int target) {
int length=nums.size();
int left=0;
int mid;
int right=length-1;
//如果target在nums数组中，二分直接查找
while (left {
mid=(right+mid)/2;
if (target==nums[mid])
return mid;
else if (target right=mid-1;
else
left=mid+1;
}
//如果target的值，比nums数组中的值都大
if (target>nums[left])
return left+1;
//如果target的值，比nums数组中的值都小
return left;
}
};
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net
