问题描述
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
第一种方法思路简单，暴力搜索，但是时间复杂度为O（n）。
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) { return i; } } return len ; } };第二种是二分法，需要注意的是下标不要弄错。
class Solution { public: int searchInsert(vector<int>& nums, int target) { int first = 0; int last = nums.size() - 1; int mid = (first + last) / 2; if (nums.empty())return 0; else if (nums.back() < target)//若没有这个分支，当数组最大元素小于目标值时，返回出错 return nums.size(); else { while (nums[mid] != target && first != last) { if (nums[mid] > target) last = mid; else first = mid + 1; mid = (first + last) / 2; } if (nums[mid] == target) return mid; else return first; } } }; int main() { Solution list; vector<int>nums; int a, target; while (cin >> a) { nums.push_back(a); if (getchar() == '\n') break; } cin >> target; int result = list.searchInsert(nums, target); cout << result<< " "; }
