LeetCode——035

/*
35. Search Insert Position My Submissions QuestionEditorial Solution
Total Accepted: 102229 Total Submissions: 274634 Difficulty: Medium
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

Subscribe to see which companies asked this question
*/

/*
解题思路：
方法一：使用STL 下界函数lower_bound
方法二：使用二分查找法（注意left与right的关系有无等号）
方法三：直接从头开始查找
*/

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {

        //方法一：由上一题可知，可以应用下边界函数来求
        //return lower_bound(nums.begin(),nums.end(),target)-nums.begin();

        //方法二：此题想考察的是折半查找
        if(nums.back()<target)return nums.size();
        int left=0,right=nums.size()-1;

        while(left<right){
            int mid=left+(right-left)/2;
            if(nums[mid]==target)return mid;
            else if(nums[mid]<target)left=mid+1;
            else right=mid;

        }
        return right;

        //方法三：直接从头查找
       /*   for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] >= target) return i;
        }
        return nums.size();
       */


    }
};