LeetCode OJ：Search Insert Position（查找插入位置）

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

首先是自己一个比较蠢的方法，可能当时没怎么细细的想，大体的思路就是，将vector中元素存放到set中（因为set插入的时候已经排好序了），首先查找，找不到的话在插入，并且记下插入位置，指针递增到那个地方的时候就找到了那个位置。如果第一次找到那个位置的就直接递增找到那个位置即可，代码见下，很不优雅：

 1 class Solution {
 2 public:
 3     int searchInsert(vector<int>& nums, int target) {
 4         set<int>tmpSet(nums.begin(), nums.end());//因为set已经排好序了，所以用set
 5         int i = 0;
 6         set<int>::iterator sItor;
 7         if((sItor = (tmpSet.find(target))) == tmpSet.end())//不在set中的话，就先插入
 8             sItor = tmpSet.insert(target);
 9         for(auto itor = tmpSet.begin(); itor != it.first; ++itor){
10             i++;   
11         return i;
12     }
13 };

但是其实在网上找了点好的答案，实际上这个就是二分法的一个小小的变形而已：

 1 class Solution {
 2 public:
 3     int searchInsert(vector<int>& nums, int target) {
 4         int beg = 0;
 5         int end = nums.size() - 1;
 6         int mid;
 7         while(beg <= end){
 8             mid = (beg + end) >> 1;
 9             if(nums[mid] > target)
10                 end = mid - 1;
11             else if(nums[mid] < target)
12                 beg = mid + 1;
13             else
14                 return mid;
15         }
16         int sz = nums.size();
17         if(end < 0) reutrn 0;    //这个地方应该注意，不要搞反了
18         if(beg >= sz) reutrn sz;
19         return beg;    //这一步应该注意，很关键
21     }
22 };

二分法不可小觑，细节还是很多的，仔细看看都能有不小的收获。其实实际上感觉写出来不太容易错的还是上面写的那种方法，不过那个总杆觉写出来怪怪的，不合题目的初衷了都。

java代码如下所示：

 1 public class Solution {
 2     public int searchInsert(int[] nums, int target) {
 3         int beg = 0;
 4         int end = nums.length - 1;
 5         while(beg <= end){
 6             int mid = beg + (end - beg)/2;
 7             if(nums[mid] > target)
 8                 end--;
 9             else if(nums[mid] < target)
10                 beg++;
11             else
12                 return mid;
13         }
14         if(beg >= nums.length)
15             return nums.length;
16         if(end < 0)
17             return 0;
18         return beg;
19     }
20 }