LeetCode T35

思路1：直接前向遍历一次，搜到相等或大于就返回该位置

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int len =  nums.size();for(int i = 0 ; i < len; i++){if((nums[i] == target) || (nums[i] > target)) return i;}return -1;}
};

思路2：二分法

二分法是本题考试的知识点。

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1, mid;while (left <= right){mid = (left + right)/2;if (nums[mid] > target) right = mid - 1;else if (nums[mid] < target) left = mid + 1;else return mid;}return left; }
};

其中，（left + right）/ 2 只取整数部分，舍弃小数部分，不会四舍五入。

二分法的思想是根据移动规则，每次让左或右指针向中间逼近。right = mid-1正好是使right指针左移一位，left = mid+1正好是使left指针右移一位。left和right的移动规则是二分问题的模板。

LeetCode T35

思路1：直接前向遍历一次，搜到相等或大于就返回该位置

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int len =  nums.size();for(int i = 0 ; i < len; i++){if((nums[i] == target) || (nums[i] > target)) return i;}return -1;}
};

思路2：二分法

二分法是本题考试的知识点。

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1, mid;while (left <= right){mid = (left + right)/2;if (nums[mid] > target) right = mid - 1;else if (nums[mid] < target) left = mid + 1;else return mid;}return left; }
};

其中，（left + right）/ 2 只取整数部分，舍弃小数部分，不会四舍五入。

二分法的思想是根据移动规则，每次让左或右指针向中间逼近。right = mid-1正好是使right指针左移一位，left = mid+1正好是使left指针右移一位。left和right的移动规则是二分问题的模板。