LeetCode35.搜索插入位置
//个人学习笔记用
- 题目:
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
参考题解--代码随想录
-
暴力解法:
class Solution { public: int searchInsert(vector<int>& nums, int target) { for(int i = 0; i< nums.size();i++){ if (nums[i] >= target){ return i; } } return nums.size(); } }; //解析:他是要返回位置,所以可以不用插入数据,直接返回位置即可
-
二分解法
class Solution { public: int searchInsert(vector<int>& nums, int target) { if(nums.empty()) return 0; int left = 0; int right = nums.size() - 1; while(left <= right){ //int middle = (left + right)/2; int middle = left + ((right - left)/2); //左右变量一直在变化,那么要计算middle就要在循环里面定义,即随着left 、right的变化,middle也在变化 if(nums[middle] < target) left = middle + 1; else if(nums[middle] > target) right = middle -1; else return middle; } return right + 1; } }; //解析:他是要返回位置,所以可以不用插入数据,直接返回位置即可