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;
  	}
  };
  
  //解析：他是要返回位置，所以可以不用插入数据，直接返回位置即可
  
  

热门相关：超武穿梭   夫人你马甲又掉了   梦回大明春   梦回大明春   最强反套路系统