LeetCode35.搜索插入位置

//个人学习笔记用

• 题目：
  给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
  请必须使用时间复杂度为 O(log n) 的算法。
  

参考题解--代码随想录

• 暴力解法：
  1. class Solution {
  2. public:
  3.     int searchInsert(vector<int>& nums, int target) {
  4.             for(int i  = 0; i< nums.size();i++){
  5.                 if (nums[i] >= target){
  6.                 return i;
  7.                 }
  8.             }
  9.             return nums.size();
  10. }
  11. };
  13. //解析：他是要返回位置，所以可以不用插入数据，直接返回位置即可

  复制代码
• 二分解法
  1. class Solution {
  2. public:
  3.         int searchInsert(vector<int>& nums, int target) {
  4.     if(nums.empty())
  5.     return 0;
  6.     int left = 0;
  7.     int right = nums.size() - 1;
  8.     while(left <= right){
  9.         //int middle = (left + right)/2;
  10.         int middle = left + ((right - left)/2);  
  11. //左右变量一直在变化，那么要计算middle就要在循环里面定义，即随着left 、right的变化，middle也在变化
  12.                 if(nums[middle] < target)
  13.                 left = middle + 1;
  14.                 else if(nums[middle] > target)
  15.                 right = middle -1;
  16.                 else
  17.             return middle;
  18.             }
  19.       return right + 1;
  20.         }
  21. };
  23. //解析：他是要返回位置，所以可以不用插入数据，直接返回位置即可

  复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！