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

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