35. 搜索插入位置&& 二分查找法

1.暴力搜索就完事

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

2.二分查找…这些用例跑出来跟暴力差不多 主要就是用left right缩小区间 用「排除法」（减治思想）写二分查找问题、与其它二分查找模板的比较

class Solution { public: int searchInsert(vector<int> &nums, int target) { int size = nums.size(); if (size == 0) { return 0; } // 特判 if (nums[size - 1] < target) { return size; } int left = 0; int right = size - 1; while (left < right) { int mid = left + (right - left) / 2; // 严格小于 target 的元素一定不是解 if (nums[mid] < target) { // 下一轮搜索区间是 [mid + 1, right] left = mid + 1; } else { right = mid; } } return left; } };